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

Трансформация массива положительных целых чисел $$$a_1,a_2,\dots,a_n$$$ определена как замена $$$a$$$ на массив $$$b_1,b_2,\dots,b_n$$$, получающийся операцией $$$b_i=a_i\oplus a_{(i\bmod n)+1}$$$, где $$$\oplus$$$ обозначает операцию побитового XOR (исключающего ИЛИ).

Вам даны целые числа $$$n$$$, $$$t$$$ и $$$w$$$. Мы считаем, что массив $$$c_1,c_2,\dots,c_n$$$ ($$$0 \le c_i \le 2^w-1$$$) является бугабу тогда и только тогда, когда существует массив $$$a_1,a_2,\dots,a_n$$$ такой, что после трансформации массива $$$a$$$ ровно $$$t$$$ раз массив $$$a$$$ превращается в $$$c$$$.

Например, если $$$n=6$$$, $$$t=2$$$, $$$w=2$$$, то массив $$$[3,2,1,0,2,2]$$$ — бугабу, потому что его можно получить, трансформировав массив $$$[2,3,1,1,0,1]$$$ $$$2$$$ раза: $$$$$$ [2,3,1,1,0,1]\to [2\oplus 3,3\oplus 1,1\oplus 1,1\oplus 0,0\oplus 1,1\oplus 2]=[1,2,0,1,1,3]; \\ [1,2,0,1,1,3]\to [1\oplus 2,2\oplus 0,0\oplus 1,1\oplus 1,1\oplus 3,3\oplus 1]=[3,2,1,0,2,2]. $$$$$$

Массив $$$[4,4,4,4,0,0]$$$ не бугабу, потому что $$$4 > 2^2 - 1$$$. Массив $$$[2,3,3,3,3,3]$$$ не бугабу, потому что он не может быть получен трансформацией одного массива $$$2$$$ раза.

Вам дан массив $$$c$$$, значения на некоторых позициях которого неизвестны (вначале только $$$m$$$ элементов известны, остальные — нет). Также есть $$$q$$$ модификаций, где каждая модификация меняет какой-либо элемент $$$c$$$. Модификация может изменить, известен ли элемент на какой-либо позиции или нет, а так же, возможно, переопределить элемент на позиции, которая уже известна.

Вам нужно посчитать, сколько возможных массивов $$$c$$$ (с произвольными элементами на неизвестных позициях) являются бугабу после каждой модификации. Выведите $$$i$$$-й ответ по модулю $$$p_i$$$ ($$$p_i$$$ — заданный массив из $$$q$$$ элементов).

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

Первая строка содержит четыре целых числа $$$n$$$, $$$m$$$, $$$t$$$ и $$$w$$$ ($$$2\le n\le 10^7$$$, $$$0\le m\le \min(n, 10^5)$$$, $$$1\le t\le 10^9$$$, $$$1\le w\le 30$$$).

Затем следуют $$$m$$$ строк, $$$i$$$-я из которых содержит два целых числа $$$d_i$$$ и $$$e_i$$$ ($$$1\le d_i\le n$$$, $$$0\le e_i< 2^w$$$), означающие, что позиция $$$d_i$$$ массива $$$c$$$ известна и $$$c_{d_i}=e_i$$$. Гарантируется, что $$$1\le d_1<d_2<\ldots<d_m\le n$$$.

Следующая строка содержит одно число $$$q$$$ ($$$1\le q\le 10^5$$$) — количество модификаций.

Затем следуют $$$q$$$ строк, $$$i$$$-я из которых содержит три целых числа $$$f_i$$$, $$$g_i$$$, $$$p_i$$$ ($$$1\le f_i\le n$$$, $$$-1\le g_i< 2^w$$$, $$$11\le p_i\le 10^9+7$$$). Значение $$$g_i=-1$$$ означает пометку позиции $$$f_i$$$ массива $$$c$$$ как неизвестной, иначе пометку позиции $$$f_i$$$ массива $$$c$$$ как известной, причем $$$c_{f_i}=g_i$$$. Значение $$$p_i$$$ означает, что вы должны вывести $$$i$$$-й ответ по модулю $$$p_i$$$.

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

Выведите $$$q$$$ строк — ваши ответы.

Примеры
Входные данные
3 2 1 1
1 1
3 1
4
2 0 123456789
2 1 111111111
1 -1 987654321
3 -1 555555555
Выходные данные
1
0
1
2
Входные данные
24 8 5 4
4 4
6 12
8 12
15 11
16 7
20 2
21 9
22 12
13
2 13 11
3 15 12
5 7 13
9 3 14
10 5 15
11 15 16
13 14 17
14 1 18
18 9 19
19 6 20
23 10 21
24 8 22
21 13 23
Выходные данные
1
4
9
2
1
0
1
10
11
16
16
0
16
Примечание

В первом примере $$$n=3$$$, $$$t=1$$$ и $$$w=1$$$. Пусть $$$?$$$ обозначает неизвестную позицию в массиве $$$c$$$.

В первом запросе $$$c=[1,0,1]$$$. Единственный возможный массив $$$[1,0,1]$$$ — бугабу, потому что он может быть получен одной трансформацией из $$$[0,1,1]$$$. Поэтому ответ $$$1\bmod 123\,456\,789 = 1$$$.

Во втором запросе $$$c=[1,1,1]$$$. Единственный возможный массив $$$[1,1,1]$$$ — не бугабу. Поэтому ответ $$$0\bmod 111\,111\,111 = 0$$$.

В третьем запросе $$$c=[?,1,1]$$$. Есть два возможных массива: $$$[1,1,1]$$$ и $$$[0,1,1]$$$. Из них только $$$[0,1,1]$$$ является бугабу, потому что может быть получен одной трансформацией из $$$[1,1,0]$$$. Поэтому ответ $$$1\bmod 987\,654\,321=1$$$.

В четвертом запросе $$$c=[?,1,?]$$$. Есть четыре возможных массива, из них $$$[0,1,1]$$$ и $$$[1,1,0]$$$ являются бугабу. $$$[1,1,0]$$$ может быть получен из $$$[1,0,1]$$$ одной трансформацией. Поэтому ответ $$$2\bmod 555\,555\,555=2$$$.