You have been gifted a magic sequence of integers: $$$a_1, a_2, \ldots, a_n$$$. However, this is no ordinary sequence — it can modify itself in a specific way!

After observing it carefully, you discovered the rule it follows:

Repeatedly, two indices $$$1 \le i \le j \le n$$$ are chosen.
Then, the value at index $$$j$$$ is updated as: $$$a_j \leftarrow a_j \oplus a_i$$$.$$$^{\text{∗}}$$$

Being afraid of strictly increasing sequences, you start asking yourself questions:

You are given $$$q$$$ queries. Each query consists of two integers $$$l$$$ and $$$r$$$, and you must determine whether the subarray $$$a_l, a_{l+1}, \ldots, a_r$$$ can be transformed into a strictly increasing sequence by applying any number of the described operations only within the range $$$l$$$ to $$$r$$$, that is, only using indices $$$l \le i \le j \le r$$$.

$$$^{\text{∗}}$$$$$$\oplus$$$ denotes the bitwise XOR operation.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n, q \leq 2 \cdot 10^5$$$) — the length of the sequence and the number of queries.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \lt 2^{20}$$$) — the contents of the sequence.

Each of the next $$$q$$$ lines contains two integers $$$l$$$ and $$$r$$$ ($$$1 \leq l \leq r \leq n$$$), representing a query. For each query, you must determine whether the subarray $$$a_l, a_{l+1}, \ldots, a_r$$$ can be transformed into a strictly increasing sequence using the allowed operations.

It is guaranteed that the total sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$, and the total sum of $$$q$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each query, output YES if the subarray $$$a_l, a_{l+1}, \ldots, a_r$$$ can be transformed into a strictly increasing sequence using the allowed operations; otherwise, output NO.

You may print each letter of YES or NO in any case. For example, YES, yES, YeS will all be recognized as a positive answer.

Note

In the first test case:

For the first query, the sequence is $$$[1]$$$, which is increasing, so no changes are needed.

For the second query, the sequence is $$$[1, 2]$$$, which is also increasing, no changes required.

For the third query the seqeunce is $$$[1, 2, 2]$$$ which is not strictly increasing so we have to make some operations. If we apply $$$i = 1, j = 3$$$ then $$$a_3 \leftarrow a_3 \oplus a_1$$$. The sequence becomes $$$[1, 2, 3]$$$ which is now strictly increasing. Thus, the answer is positive.

For the fourth query the sequence is $$$[1, 2, 2, 1]$$$. We can do the following:

$$$a_2 \leftarrow a_2 \oplus a_2 (i = 2, j = 2)$$$. The seqeuence becomes $$$[1, 0, 2, 1]$$$.
$$$a_4 \leftarrow a_4 \oplus a_3 (i = 3, j = 4)$$$. The sequence becomes $$$[1, 0, 2, 3]$$$.
$$$a_2 \leftarrow a_2 \oplus a_1 (i = 1, j = 2)$$$. The sequence becomes $$$[1, 1, 2, 3]$$$.
$$$a_1 \leftarrow a_1 \oplus a_1 (i = 1, j = 1)$$$. The sequence becomes $$$[0, 1, 2, 3]$$$ which is strictly increasing.

In the second test case:

For the first query, it is not possible to make the entire sequence strictly increasing.

For the second query, the sequence is $$$[1]$$$, which is already strictly increasing, so no changes are needed.

In the third query, the sequence is $$$[1, 1]$$$. We can make it strictly increasing by choosing $$$i = j = 2$$$ (referring to the indices in the original sequence) and performing the operation $$$a_2 \leftarrow a_2 \oplus a_2$$$. This sets $$$a_2 = 0$$$, resulting in the subarray from index 2 to 3 becoming $$$[0, 1]$$$, which is strictly increasing.

For the final query, we can perform the following operations in this order:

$$$a_6 \leftarrow a_6 \oplus a_5$$$
$$$a_7 \leftarrow a_7 \oplus a_5$$$
$$$a_5 \leftarrow a_5 \oplus a_5$$$

After these operations, the subarray from index 5 to 8 becomes $$$[0, 1, 2, 3]$$$, which is strictly increasing.

Idx	Name	Rating
A	All Lengths Subtraction	800
B	Discounts	1000
C	Max Tree	1300
D1	Inversion Graph Coloring (Easy Version)	1800
D2	Inversion Graph Coloring (Hard Version)	2200
E	Make Good	2400
F	Increasing Xor	2700

Codeforces Round 1051 (Div. 2)