Bugaboo
Contest: Codeforces Round 808 (Div. 1)
Difficulty rating: 3500
Tags: bitmasks, constructive algorithms, dp, number theory

A transformation of an array of positive integers $$$a_1,a_2,\dots,a_n$$$ is defined by replacing $$$a$$$ with the array $$$b_1,b_2,\dots,b_n$$$ given by $$$b_i=a_i\oplus a_{(i\bmod n)+1}$$$, where $$$\oplus$$$ denotes the bitwise XOR operation.

You are given integers $$$n$$$, $$$t$$$, and $$$w$$$. We consider an array $$$c_1,c_2,\dots,c_n$$$ ($$$0 \le c_i \le 2^w-1$$$) to be bugaboo if and only if there exists an array $$$a_1,a_2,\dots,a_n$$$ such that after transforming $$$a$$$ for $$$t$$$ times, $$$a$$$ becomes $$$c$$$.

For example, when $$$n=6$$$, $$$t=2$$$, $$$w=2$$$, then the array $$$[3,2,1,0,2,2]$$$ is bugaboo because it can be given by transforming the array $$$[2,3,1,1,0,1]$$$ for $$$2$$$ times:

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

And the array $$$[4,4,4,4,0,0]$$$ is not bugaboo because $$$4 > 2^2 - 1$$$. The array $$$[2,3,3,3,3,3]$$$ is also not bugaboo because it can't be given by transforming one array for $$$2$$$ times.

You are given an array $$$c$$$ with some positions lost (only $$$m$$$ positions are known at first and the remaining positions are lost). And there are $$$q$$$ modifications, where each modification is changing a position of $$$c$$$. A modification can possibly change whether the position is lost or known, and it can possibly redefine a position that is already given.

You need to calculate how many possible arrays $$$c$$$ (with arbitrary elements on the lost positions) are bugaboos after each modification. Output the $$$i$$$-th answer modulo $$$p_i$$$ ($$$p_i$$$ is a given array consisting of $$$q$$$ elements).

Input format:
The first line contains four integers $$$n$$$, $$$m$$$, $$$t$$$ and $$$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$$$).

The $$$i$$$-th line of the following $$$m$$$ lines contains two integers $$$d_i$$$ and $$$e_i$$$ ($$$1\le d_i\le n$$$, $$$0\le e_i< 2^w$$$). It means the position $$$d_i$$$ of the array $$$c$$$ is given and $$$c_{d_i}=e_i$$$. It is guaranteed that $$$1\le d_1<d_2<\ldots<d_m\le n$$$.

The next line contains only one number $$$q$$$ ($$$1\le q\le 10^5$$$) — the number of modifications.

The $$$i$$$-th line of the following $$$q$$$ lines contains three integers $$$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$$$). The value $$$g_i=-1$$$ means changing the position $$$f_i$$$ of the array $$$c$$$ to a lost position, otherwise it means changing the position $$$f_i$$$ of the array $$$c$$$ to a known position, and $$$c_{f_i}=g_i$$$. The value $$$p_i$$$ means you need to output the $$$i$$$-th answer modulo $$$p_i$$$.

Output format:
The output contains $$$q$$$ lines, denoting your answers.

Constraints:
Time limit: 2.0 s
Memory limit: 1024.0 MB

Note:
In the first example, $$$n=3$$$, $$$t=1$$$, and $$$w=1$$$. Let $$$?$$$ denote a lost position of $$$c$$$.

In the first query, $$$c=[1,0,1]$$$. The only possible array $$$[1,0,1]$$$ is bugaboo because it can be given by transforming $$$[0,1,1]$$$ once. So the answer is $$$1\bmod 123\,456\,789 = 1$$$.

In the second query, $$$c=[1,1,1]$$$. The only possible array $$$[1,1,1]$$$ is not bugaboo. So the answer is $$$0\bmod 111\,111\,111 = 0$$$.

In the third query, $$$c=[?,1,1]$$$. There are two possible arrays $$$[1,1,1]$$$ and $$$[0,1,1]$$$. Only $$$[0,1,1]$$$ is bugaboo because it can be given by transforming $$$[1,1,0]$$$ once. So the answer is $$$1\bmod 987\,654\,321=1$$$.

In the fourth query, $$$c=[?,1,?]$$$. There are four possible arrays. $$$[0,1,1]$$$ and $$$[1,1,0]$$$ are bugaboos. $$$[1,1,0]$$$ can be given by performing $$$[1,0,1]$$$ once. So the answer is $$$2\bmod 555\,555\,555=2$$$.

Example input:
3 2 1 1
1 1
3 1
4
2 0 123456789
2 1 111111111
1 -1 987654321
3 -1 555555555

Example output:
1
0
1
2

Example input:
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

Example output:
1
4
9
2
1
0
1
10
11
16
16
0
16

Editorial:
We can first solve an easier condition when $$$n=2^h(h\ge 0)$$$.
We know for any array $$$a_1,a_2,\ldots,a_{2^h}$$$, transforming it for $$$2^h$$$ times $$$a_i=0$$$. If you transform it more than $$$2^h$$$ times it is also guaranteed that $$$a_i=0$$$. So in this condition, if $$$t\ge 2^h$$$, we only need to test whether for all $$$i$$$, $$$c_i$$$ can be $$$0$$$.
When $$$t<2^h$$$, if transforming an array $$$a_1,a_2,\ldots,a_n$$$ for $$$t$$$ times $$$a$$$ becomes $$$c$$$, then it can be proved that $$$\bigoplus\limits_{i=1}^{2^h}a_i$$$ depends on $$$t,h$$$ and the array $$$c$$$. We can let $$$f(t,h,c_1,c_2,\ldots,c_{2^h})=\bigoplus\limits_{i=1}^{2^h}a_i$$$.
Proof: When $$$h=0$$$, $$$t$$$ must be $$$0$$$, so $$$f(t,h,c_1)=c_1$$$. When $$$h>0$$$, $$$f(t,h,c_1,c_2,\ldots,c_{2^h})$$$ can be given by $$$f(\lfloor\frac{t}{2}\rfloor,h-1,c_1,c_3,\ldots,c_{2^h-1})$$$ and $$$f(\lfloor\frac{t}{2}\rfloor,h-1,c_2,c_4,\ldots,c_{2^h})$$$. The specific process is below. If $$$t$$$ is an even number, then we know transforming $$$a_1,a_3,\ldots,a_{2^h-1}$$$ for $$$\frac{t}{2}$$$ times it becomes $$$c_1,c_3,\ldots,c_{2^h-1}$$$. Also transforming $$$a_2,a_4,\ldots,a_{2^h}$$$ for $$$\frac{t}{2}$$$ times it becomes $$$c_2,c_4,\ldots,c_{2^h}$$$. So in this case, $$$f(t,h,c_1,c_2,\ldots,c_{2^h})=f(\lfloor\frac{t}{2}\rfloor,h-1,c_1,c_3,\ldots,c_{2^h-1})\oplus f(\lfloor\frac{t}{2}\rfloor,h-1,c_2,c_4,\ldots,c_{2^h})$$$. If $$$t$$$ is an odd number, then we can first transform $$$a$$$ once, then it becomes the even number case. That is to say, $$$a$$$ now becomes $$$a_1\oplus a_2,a_2\oplus a_3,\ldots,a_{2^h}\oplus a_1$$$. Transforming $$$a_1\oplus a_2,a_3\oplus a_4,\ldots,a_{2^h-1}\oplus a_{2^h}$$$ for $$$\lfloor\frac{t}{2}\rfloor$$$ times it becomes $$$c_1,c_3,\ldots,c_{2^h-1}$$$. Transforming $$$a_2\oplus a_3,a_4\oplus a_5,\ldots,a_{2^h}\oplus a_1$$$ for $$$\lfloor\frac{t}{2}\rfloor$$$ times it becomes $$$c_2,c_4,\ldots,c_{2^h}$$$. So in this case, $$$f(t,h,c_1,c_2,\ldots,c_{2^h})=f(\lfloor\frac{t}{2}\rfloor,h-1,c_1,c_3,\ldots,c_{2^h-1})=f(\lfloor\frac{t}{2}\rfloor,h-1,c_2,c_4,\ldots,c_{2^h})$$$.
Actually the process above can inspire us to find an easy way to judge whether an array is a bugaboo. We just need to use divide and conquer to calculate $$$f(t,h,c_1,\ldots,c_{2^h})$$$ .When it becomes the second case, judge whether $$$f(\lfloor\frac{t}{2}\rfloor,h-1,c_1,c_3,\ldots,c_{2^h-1})=f(\lfloor\frac{t}{2}\rfloor,h-1,c_2,c_4,\ldots,c_{2^h})$$$. If and only if all the requirements are met, the array $$$c$$$ is a bugaboo.
And the good news is that it can be used to calculate the number of bugaboos. Let $$$dp(t,h,d_1,d_2,\ldots,d_{2^h},k)=$$$ the number of arrays $$$c_{d_1},c_{d_2},\ldots,c_{d_{2^h}}$$$ which are bugaboos and $$$f(t,h,c_{d_1},c_{d_2},\ldots,c_{d_{2^h}})=k$$$. Just like the process above, when $$$t$$$ is an even number, $$$dp(t,h,d_1,d_2,\ldots,d_{2^h},k)=\sum\limits_{l=0}^{2^w-1}dp(\lfloor\frac{t}{2}\rfloor,h-1,d_1,d_3,\ldots,d_{2^h-1},l)\cdot dp(\lfloor\frac{t}{2}\rfloor,h-1,d_2,d_4,\ldots,d_{2^h},k\oplus l)$$$; When $$$t$$$ is an odd number, $$$dp(t,h,d_1,d_2,\ldots,d_{2^h},k)=dp(\lfloor\frac{t}{2}\rfloor,h-1,d_1,d_3,\ldots,d_{2^h-1},k)\cdot dp(\lfloor\frac{t}{2}\rfloor,h-1,d_2,d_4,\ldots,d_{2^h},k)$$$.When $$$c_d$$$ is lost, $$$dp(0,0,d,k)=1$$$. When $$$c_d=k_0$$$, $$$dp(0,0,d,k)=[k=k_0]$$$. The answer is $$$\sum\limits_{k=0}^{2^w-1}dp(t,h,1,2,\ldots,2^h,k)$$$.
However, $$$2^w$$$ is so huge that we cannot do it in a short time. After some careful observations, we can surprisingly find that for $$$dp(t,h,d_1,d_2,\ldots,d_{2^h},?)$$$ either $$$\forall k,dp(t,h,d_1,d_2,\ldots,d_{2^h},k)=(2^w)^A$$$, or $$$\forall k,dp(t,h,d_1,d_2,\ldots,d_{2^h},k)=[k=B]\cdot(2^w)^C$$$, or $$$\forall k,dp(t,h,d_1,d_2,\ldots,d_{2^h},k)=0$$$. We can use this to simplify our process, making our time complexity free from $$$w$$$.
By the way, the divide and conquer process above is very similar to FFT. That is to say, we can reverse the indexes' binary bit to make the process faster.
So, when $$$n=2^h$$$, without modifications we can work out the answer in $$$O(n)$$$. And the process is just like the structure of segment tree, so we can do a modification in $$$O(\log n)$$$. The total time complexity is $$$O(n+(m+q)\log n)$$$.
When $$$n$$$ cannot be given by $$$2^h$$$, we can simply let $$$h$$$ be the lowest bit of $$$n$$$, that is to say, $$$n=2^h\cdot o$$$($$$o$$$ is an odd number). Then we can consider $$$i,i+2^h,\ldots,i+2^h\cdot(o-1)$$$ as a whole to do the process above. The only thing we need to notice is that when $$$t>2^h$$$, the requirement is that for all $$$i$$$, $$$\bigoplus\limits_{l=0}^{o-1}c_{i+2^h\cdot l}$$$ can be $$$0$$$.
Now we can solve the problem in $$$O(n+(m+q)\log n)$$$.