D. Dull game
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ним — игра, в которой два игрока по очереди берут предметы, разложенные на несколько кучек. За один ход может быть взято любое количество предметов (большее нуля) из одной кучки. Выигрывает игрок, взявший последний предмет.

Пусть у вас есть кучки с размерами $$$a_0, a_1, \dots, a_n$$$. Необходимо найти подпоследовательность кучек $$$S$$$ для которой выполняются следующие требования:

  • В игре «ним» с использованием предметов из этой подпоследовательности первый игрок проигрывает при оптимальной игре обоих.
  • $$$a_0 \in S$$$.

Вам также необходимо обработать $$$m$$$ запросов модификации последовательности кучек: $$$i$$$-й запрос $$$p_i$$$, $$$x_i$$$ означает, что с этого момента $$$a_{p_i} = x_i$$$. После каждого запроса необходимо найти подпоследовательность $$$S_i$$$ с условием, описанным выше.

Гарантируется, что изначально, а так же после каждого запроса модификации, количество подходящих подпоследовательностей кучек $$$S$$$ будет ровно одно.

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

В первой строке входных данных содержатся два целых числа $$$n$$$ и $$$m$$$.

Во второй строке входных данных содержится $$$n + 1$$$ целое число $$$a_0, a_1, \dots, a_n$$$.

Следующие $$$m$$$ строк содержат описание запросов модификации, $$$i$$$-я строка содержит два целых числа $$$t_i, x_i$$$. Для получения $$$p_i$$$ вам необходим ваш ответ на предыдущий запрос. А именно, если в качестве ответа на предыдущий запрос вы вывели числа $$$k, b_1, b_2, \dots, b_k$$$, то $$$p_i = t_i \oplus k \oplus b_1 \oplus b_2 \oplus \dots \oplus b_k$$$.

$$$$$$ 2 \le n \le 1000 $$$$$$ $$$$$$ 0 \le m \le 1000 $$$$$$ $$$$$$ 0 \le a_0, a_1, \dots a_n \lt 2^n $$$$$$ $$$$$$ 0 \le p_i \le n $$$$$$ $$$$$$ 0 \le x_i \lt 2^n $$$$$$

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

В первой строке выведите целое число $$$k$$$ — размер подпоследовательности $$$S$$$.

Во второй строке выведите последовательность $$$b_1 \lt b_2 \lt \dots \lt b_k$$$ разделенную пробелами, такую, что $$$S = {a_{b_1}, a_{b_2}, \dots, a_{b_k}}$$$.

Далее, после $$$i$$$-го запроса выведите подпоследовательность $$$S_i$$$ в таком же формате.

Примеры
Входные данные
3 1
5 6 2 7
0 3
Выходные данные
3
0 2 3 
3
0 1 2
Входные данные
3 2
1 2 3 4
0 2
2 6
Выходные данные
3
0 1 2 
2
0 1 
3
0 1 3