Day of the Programmer- HackerRank problem

 C1. Skibidus and Fanum Tax (easy version)

time limit per test

2 seconds

memory limit per test

256 megabytes

This is the easy version of the problem. In this version, m=1$m=1$.

Skibidus has obtained two arrays a$a$ and b$b$, containing n$n$ and m$m$ elements respectively. For each integer i$i$ from 1$1$ to n$n$, he is allowed to perform the operation at most once:

• Choose an integer j$j$ such that 1≤j≤m$1\le j\le m$. Set ai:=bj−ai$a_i:=b_j-a_i$. Note that ai$a_i$ may become non-positive as a result of this operation.

Skibidus needs your help determining whether he can sort a$a$ in non-decreasing order∗${}^{\text{∗}}$ by performing the above operation some number of times.

∗${}^{\text{∗}}$a$a$ is sorted in non-decreasing order if a1≤a2≤…≤an$a_1\le a_2\le \dots \le a_n$.

Input

The first line contains an integer t$t$ (1≤t≤104$1\le t\le {10}^4$) — the number of test cases.

The first line of each test case contains two integers n$n$ and m$m$ (1≤n≤2⋅105$1\le n\le 2\cdot {10}^5$, m = 1$\mathbf{\text{m = 1}}$).

The following line of each test case contains n$n$ integers a1,a2,…,an$a_1,a_2,\dots ,a_n$ (1≤ai≤109$1\le a_i\le {10}^9$).

The following line of each test case contains m$m$ integers b1,b2,…,bm$b_1,b_2,\dots ,b_m$ (1≤bi≤109$1\le b_i\le {10}^9$).

It is guaranteed that the sum of n$n$ and the sum of m$m$ over all test cases does not exceed 2⋅105$2\cdot {10}^5$.

Output

For each test case, if it is possible to sort a$a$ in non-decreasing order, print "YES" on a new line. Otherwise, print "NO" on a new line.

You can output the answer in any case. For example, the strings "yEs", "yes", and "Yes" will also be recognized as positive responses.

Example

Input

Copy

5
1 1
5
9
3 1
1 4 3
3
4 1
1 4 2 5
6
4 1
5 4 10 5
4
3 1
9 8 7
8

Output

Copy

YES
NO
YES
NO
YES

Note

In the first test case, [5]$[5]$ is already sorted.

In the second test case, it can be shown that it is impossible.

In the third test case, we can set a3:=b1−a3=6−2=4$a_3:=b_1-a_3=6-2=4$. The sequence [1,4,4,5]$[1,4,4,5]$ is in nondecreasing order.

In the last case, we can apply operations on each index. The sequence becomes [−1,0,1]$[-1,0,1]$, which is in nondecreasing order.

Solution by java Solution by python