A15186. Bugaboo

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]. $$ </p><p>And the array $\[4,4,4,4,0,0\]$ is not bugaboo because $4 &gt; 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.</p><p>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.</p><p>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).

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

The output contains $q$ lines, denoting your answers.

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