CF2143F Increasing Xor

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](https://en.wikipedia.org/wiki/Bitwise_operation#XOR).

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 < 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 $ .

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.

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.