CF1707F.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\].

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.

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

对一个正整数数组 $a_1,a_2,\dots,a_n$ 的一种变换定义为：将其替换为数组 $b_1,b_2,\dots,b_n$，其中 $b_i = a_i \oplus a_{(i \bmod n) + 1}$，$\oplus$ 表示按位异或运算。

给定整数 $n$、$t$ 和 $w$。我们称一个数组 $c_1,c_2,\dots,c_n$（满足 $0 \le c_i \le 2^w - 1$）是 bugaboo 的，当且仅当存在某个数组 $a_1,a_2,\dots,a_n$，使得对 $a$ 进行 $t$ 次上述变换后，结果恰好为 $c$。

例如，当 $n=6$、$t=2$、$w=2$ 时，数组 $[3,2,1,0,2,2]$ 是 bugaboo 的，因为它可通过将数组 $[2,3,1,1,0,1]$ 变换两次得到：

$$[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]$ 不是 bugaboo 的，因为 $4 > 2^2 - 1$；数组 $[2,3,3,3,3,3]$ 也不是 bugaboo 的，因为它无法由任意一个数组经两次变换得到。

现给定一个数组 $c$，其中部分位置丢失（初始仅有 $m$ 个位置已知，其余位置丢失）。另有 $q$ 次修改操作，每次修改会更改 $c$ 中某一个位置的值。一次修改可能改变该位置是“丢失”还是“已知”的状态，也可能重新定义一个原本已知的位置。

你需要在每次修改后，计算有多少种可能的数组 $c$（丢失位置可填入任意合法值）是 bugaboo 的。输出第 $i$ 个答案对 $p_i$ 取模的结果（$p_i$ 是一个给定的、含 $q$ 个元素的数组）。

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 \lt 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 \lt d_2 \lt \ldots \lt 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 \lt 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$.

第一行包含四个整数 $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 \lt 2^w$）。这表示数组 $c$ 在位置 $d_i$ 处的值已知，且 $c_{d_i}=e_i$。保证满足 $1\le d_1 \lt d_2 \lt \ldots \lt 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 \lt 2^w$，$11\le p_i\le 10^9+7$）。若 $g_i=-1$，表示将数组 $c$ 在位置 $f_i$ 处的值设为“未知”；否则表示将数组 $c$ 在位置 $f_i$ 处的值设为“已知”，且 $c_{f_i}=g_i$。$p_i$ 表示需将第 $i$ 次查询的答案对 $p_i$ 取模后输出。

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

输出包含 $q$ 行，表示你的答案。

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

在第一个例子中，$n=3$，$t=1$，$w=1$。令 $?$ 表示 $c$ 中丢失的位置。

在第一次查询中，$c=[1,0,1]$。唯一可能的数组 $[1,0,1]$ 是“bugaboo”，因为它可通过将 $[0,1,1]$ 变换一次得到。因此答案为 $1\bmod 123\,456\,789 = 1$。

在第二次查询中，$c=[1,1,1]$。唯一可能的数组 $[1,1,1]$ 不是“bugaboo”。因此答案为 $0\bmod 111\,111\,111 = 0$。

在第三次查询中，$c=[?,1,1]$。存在两个可能的数组：$[1,1,1]$ 和 $[0,1,1]$。其中仅 $[0,1,1]$ 是“bugaboo”，因为它可通过将 $[1,1,0]$ 变换一次得到。因此答案为 $1\bmod 987\,654\,321 = 1$。

在第四次查询中，$c=[?,1,?]$. 共有四个可能的数组。其中 $[0,1,1]$ 和 $[1,1,0]$ 是“bugaboo”。$[1,1,0]$ 可通过将 $[1,0,1]$ 变换一次得到。因此答案为 $2\bmod 555\,555\,555 = 2$。