F. Increasing Xor
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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.

Example
Input
2
4 4
1 2 2 1
1 1
1 2
1 3
1 4
8 6
5 1 1 2 3 2 1 3
1 8
2 2
2 3
2 6
4 8
5 8
Output
YES
YES
YES
YES
NO
YES
YES
NO
NO
YES
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:

  1. $$$a_2 \leftarrow a_2 \oplus a_2 (i = 2, j = 2)$$$. The seqeuence becomes $$$[1, 0, 2, 1]$$$.
  2. $$$a_4 \leftarrow a_4 \oplus a_3 (i = 3, j = 4)$$$. The sequence becomes $$$[1, 0, 2, 3]$$$.
  3. $$$a_2 \leftarrow a_2 \oplus a_1 (i = 1, j = 2)$$$. The sequence becomes $$$[1, 1, 2, 3]$$$.
  4. $$$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:

  1. $$$a_6 \leftarrow a_6 \oplus a_5$$$
  2. $$$a_7 \leftarrow a_7 \oplus a_5$$$
  3. $$$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.