F. BattleCows
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Фермер Джон отправляет корову участвовать в Международной Коровьей Олимпиаде, но ему слишком лень писать задачи для конкурса, поэтому он делает следующее самое разумное: организует турнир по борьбе!

У фермера Джона есть $$$2^n$$$ коров, стоящих в ряд, при этом $$$i$$$-я корова имеет уровень навыка $$$a_i$$$. Каждая корова начинает в стопке, содержащей только её саму, и уровень навыка стопки равен XOR-сумме$$$^{\text{∗}}$$$ уровней навыка всех коров в ней. Например, если стопка состоит из коров с уровнями навыка $$$1, 3, 9$$$ снизу вверх, то уровень навыка стопки равен $$$1 \oplus 3 \oplus 9 = 11$$$.

Следующий процесс повторяется до тех пор, пока не останется только одна стопка.

  • Каждая стопка на нечётной позиции ($$$1$$$-я, $$$3$$$-я и т.д.) начинает бой со стопкой справа от неё. Например, $$$1$$$-я стопка будет сражаться с $$$2$$$-й стопкой, $$$3$$$-я стопка будет сражаться с $$$4$$$-й стопкой и т.д.
  • Стопка с более высоким уровнем навыка выиграет матч, при равенстве выигрывает левая стопка.
  • Выигравшая стопка перепрыгнет на верх проигравшей стопки и сдвинет себя так, чтобы не осталось пробелов от побеждённых стопок.

Чтобы сделать это более захватывающим, фермер Джон создал $$$q$$$ зелий, так что $$$i$$$-е зелье делает уровень навыка коровы, которая его выпьет, равным $$$c_i$$$. Фермер Джон хочет протестировать свои зелья на коровах, поэтому он даёт $$$i$$$-е зелье корове $$$b_i$$$, а затем проводит турнир. Для каждого испытания фермер Джон хочет знать, сколько коров находится выше коровы, которая получила зелье, в финальной стопке.

Зелья фермера Джона быстро теряют свою силу, поэтому, когда турнир заканчивается, корова, которая получила зелье, вернёт свой уровень навыка к тому, каким он был изначально. Другими словами, все запросы независимы.

$$$^{\text{∗}}$$$XOR-сумма массива $$$x_1, x_2, \ldots, x_y$$$ равна $$$x_1 \oplus x_2 \oplus x_3 \ldots x_{y-1} \oplus x_y$$$, где $$$\oplus$$$ обозначает побитовую операцию XOR.

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

Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n \le 18$$$, $$$1 \le q \le 2 \cdot 10^5$$$) — где $$$2^n$$$ равно количеству коров в турнире, а $$$q$$$ — количество зелий.

Вторая строка содержит $$$2^n$$$ целых чисел $$$a_1, a_2, \ldots, a_{2^n}$$$ ($$$1 \le a_i \le 2^{30}$$$) — уровни навыка коров.

Следующие $$$q$$$ строк содержат по два целых числа $$$b_i$$$ и $$$c_i$$$ ($$$1 \le b_i \le 2^n$$$, $$$1 \le c_i \le 2^{30}$$$) — индекс коровы, которая получает зелье, и новый уровень навыка коровы.

Гарантируется, что сумма $$$2^n$$$ по всем наборам не превышает $$$2^{18} = 262144$$$, а сумма $$$q$$$ по всем наборам не превышает $$$2 \cdot 10^5$$$.

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

Для каждого испытания выведите, сколько коров находится выше коровы, которая получила зелье, в финальной стопке.

Пример
Входные данные
4
2 2
1 3 5 7
1 1
4 8
1 2
1 3
1 4
1 2
3 4
1 8 3 10 2 5 7 1
5 3
8 12
1 9
2 1
2 1
1 2 3 4
3 1
Выходные данные
1
0
0
1
5
0
2
3
1
Примечание

Для первого раунда первого примера уровни навыка коров не меняются, и матчи проходят следующим образом:

  • Коровы $$$1$$$ и $$$2$$$ сражаются. Поскольку уровень навыка коровы $$$2$$$ выше, чем уровень навыка коровы $$$1$$$, корова $$$2$$$ выигрывает бой, поэтому её стопка теперь содержит коров $$$1, 2$$$ в этом порядке, а уровень навыка стопки теперь $$$3 \oplus 1 = 2$$$.
  • Коровы $$$3$$$ и $$$4$$$ сражаются. Поскольку уровень навыка коровы $$$4$$$ выше, чем уровень навыка коровы $$$3$$$, корова $$$4$$$ выигрывает бой, поэтому её стопка теперь содержит коров $$$3, 4$$$ в этом порядке, а уровень навыка стопки теперь $$$7 \oplus 5 = 2$$$.
  • Две оставшиеся стопки сражаются. Поскольку уровень навыка первой стопки равен уровню навыка второй стопки, первая стопка выигрывает бой, так как её индекс ниже, чем у второй стопки, поэтому финальная стопка содержит коров $$$3, 4, 1, 2$$$ в этом порядке, а её уровень навыка теперь $$$2 \oplus 2 = 0$$$.
Поскольку мы дали зелье корове $$$1$$$, наш ответ равен $$$1$$$, так как над коровой $$$1$$$ находится одна корова.

Визуализация раунда показана ниже.

Для второго раунда первого примера уровень навыка коровы $$$4$$$ теперь $$$8$$$, и матчи проходят следующим образом:

  • Коровы $$$1$$$ и $$$2$$$ сражаются. Поскольку уровень навыка коровы $$$2$$$ выше, чем уровень навыка коровы $$$1$$$, корова $$$2$$$ выигрывает бой, поэтому её стопка теперь содержит коров $$$1, 2$$$ в этом порядке, а уровень навыка стопки теперь $$$3 \oplus 1 = 2$$$.
  • Коровы $$$3$$$ и $$$4$$$ сражаются. Поскольку уровень навыка коровы $$$4$$$ выше, чем уровень навыка коровы $$$3$$$, корова $$$4$$$ выигрывает бой, поэтому её стопка теперь содержит коров $$$3, 4$$$ в этом порядке, а уровень навыка стопки теперь $$$8 \oplus 5 = 13$$$.
  • Две оставшиеся стопки сражаются. Поскольку уровень навыка второй стопки выше, чем уровень навыка первой стопки, вторая стопка выигрывает бой, поэтому финальная стопка содержит коров $$$1, 2, 3, 4$$$ в этом порядке, а её уровень навыка теперь $$$2 \oplus 13 = 15$$$.
Поскольку мы дали зелье корове $$$4$$$, наш ответ равен $$$0$$$, так как над коровой $$$4$$$ нет коров.