F. Увеличение XOR
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам подарили волшебную последовательность целых чисел: $$$a_1, a_2, \ldots, a_n$$$. Однако это не обычная последовательность — она может изменять себя особым образом!

После внимательного наблюдения вы обнаружили правило, которому она подчиняется:

  • Выбираются два индекса $$$1 \le i \le j \le n$$$.
  • Затем значение по индексу $$$j$$$ обновляется как: $$$a_j \leftarrow a_j \oplus a_i$$$.$$$^{\text{∗}}$$$

Боясь строго возрастающих последовательностей, вы начинаете задаваться вопросами...

Вы задались $$$q$$$ вопросами. Каждый вопрос состоит из двух целых чисел $$$l$$$ и $$$r$$$, и вам нужно определить, может ли подмассив $$$a_l, a_{l+1}, \ldots, a_r$$$ быть преобразован в строго возрастающую последовательность после применения любого количества описанных операций только в пределах диапазона от $$$l$$$ до $$$r$$$, то есть, используя только индексы $$$l \le i \le j \le r$$$.

$$$^{\text{∗}}$$$$$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \leq n, q \leq 2 \cdot 10^5$$$) — длина последовательности и количество запросов.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \lt 2^{20}$$$) — содержимое последовательности.

Каждая из следующих $$$q$$$ строк содержит два целых числа $$$l$$$ и $$$r$$$ ($$$1 \leq l \leq r \leq n$$$), представляющих запрос. Для каждого запроса вам нужно определить, может ли подмассив $$$a_l, a_{l+1}, \ldots, a_r$$$ быть преобразован в строго возрастающую последовательность с использованием разрешенных операций.

Гарантируется, что общая сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$, а общая сумма $$$q$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого запроса выведите YES, если подмассив $$$a_l, a_{l+1}, \ldots, a_r$$$ может быть преобразован в строго возрастающую последовательность с использованием разрешенных операций; в противном случае выведите NO.

Вы можете выводить каждую букву YES или NO в любом регистре (строчную или заглавную). Например, строки YES, yES и YeS будут приняты как положительный ответ.

Пример
Входные данные
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
Выходные данные
YES
YES
YES
YES
NO
YES
YES
NO
NO
YES
Примечание

В первом наборе входных данных:

Для первого запроса последовательность равна $$$[1]$$$, она уже является возрастающей, поэтому никаких изменений не требуется.

Для второго запроса последовательность равна $$$[1, 2]$$$, она также уже является возрастающей, никаких изменений не требуется.

Для третьего запроса последовательность равна $$$[1, 2, 2]$$$, она не является строго возрастающей, поэтому нам нужно выполнить некоторые операции. Если мы применим $$$i = 1, j = 3$$$, то $$$a_3 \leftarrow a_3 \oplus a_1$$$. Последовательность становится равна $$$[1, 2, 3]$$$, теперь она является строго возрастающей. Таким образом, ответ положительный.

Для четвертого запроса последовательность равна $$$[1, 2, 2, 1]$$$. Мы можем сделать следующее:

  1. $$$a_2 \leftarrow a_2 \oplus a_2 (i = 2, j = 2)$$$. Последовательность становится $$$[1, 0, 2, 1]$$$.
  2. $$$a_4 \leftarrow a_4 \oplus a_3 (i = 3, j = 4)$$$. Последовательность становится $$$[1, 0, 2, 3]$$$.
  3. $$$a_2 \leftarrow a_2 \oplus a_1 (i = 1, j = 2)$$$. Последовательность становится $$$[1, 1, 2, 3]$$$.
  4. $$$a_1 \leftarrow a_1 \oplus a_1 (i = 1, j = 1)$$$. Последовательность становится $$$[0, 1, 2, 3]$$$, а следовательно, и строго возрастающей.

Во втором наборе входных данных:

Для первого запроса невозможно сделать всю последовательность строго возрастающей.

Для второго запроса последовательность равна $$$[1]$$$, она уже является строго возрастающей, поэтому никаких изменений не требуется.

В третьем запросе последовательность равна $$$[1, 1]$$$. Мы можем сделать её строго возрастающей, выбрав $$$i = j = 2$$$ (ссылаясь на индексы в исходной последовательности) и выполнив операцию $$$a_2 \leftarrow a_2 \oplus a_2$$$. Это присваивает $$$a_2 = 0$$$, в результате чего подмассив от индекса 2 до 3 становится $$$[0, 1]$$$, то есть строго возрастающим.

Для последнего запроса мы можем выполнить операции в таком порядке:

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

После этих операций подмассив с индексами от 5 до 8 становится $$$[0, 1, 2, 3]$$$, что является строго возрастающим массивом.