【烂题杯 Round 1】可持久化糖果树

感谢 @zhouhuanyi 提出本题数据过水。 **本题数据生成器经过修改，部分题解里的代码将无法通过，并非题解出现错误！**

小 A 有一棵糖果树，树上有 $n$ 个节点，编号为 $1,2,\cdots,n$。每个节点里有 $m$ 位小朋友，编号为 $1,2,\cdots,m$。每个小朋友可以进行 $k$ 次祈愿，编号为 $1,2,\cdots,k$。节点 $i$ 中的第 $j$ 位小朋友的第 $x$ 次祈愿可以获得 $a_{i,j,x}$ 个糖果。我们称未被修改的糖果树为第 $0$ 个版本树。 一个小朋友被称为开心的，当且仅当她经过 $k$ 轮祈愿后可以获得的糖果数量可以被 $3$ 整除，这样就可以把糖果平均地分给她和她的父母。也就是说，第 $i$ 个节点的第 $j$ 个小朋友是开心的当且仅当 $\sum_{x=1}^k a_{i,j,x}\bmod 3=0$。 一个节点被称为是快乐的，当且仅当上面的 $m$ 位小朋友都是开心的。 小 A 可以施加魔法：他将会有 $q$ 次修改，下标从 $1$ 开始的第 $i$ 次修改可以描述为 $(x,y,z)$，表示将第 $x$ 个版本树上所有节点中的所有小朋友的第 $y$ 次祈愿获得的糖果数量乘上 $z$，得到第 $i$ 个版本树。要求你求出每个版本树中有多少个点是快乐的。

由于输入文件过大无法上传，接下来我们将会以一种诡异的方式读入数据。 第一行有 $4$ 个整数 $n$、$m$、$k$、$X$，分别表示节点个数、每个节点上的小朋友个数、每个小朋友的祈愿次数、随机种子。 那么 $a_{i,j,x}=(X+X\times i+(X\oplus (j\times x+i\times i))\bmod 10^9$。 对于 C++，代码实现如下： ```cpp a[i][j][x] = (X + 1ll * X * i + (X ^ (1ll * j * x + 1ll * i * i))) % 1000000000; ``` 接下来一行一个正整数 $q$，表示修改次数。 对于下标从 $1$ 开始的第 $i$ 次修改，$x=(X\oplus i)\bmod i$，$y=(X\oplus i)\bmod k+1$，$z=(X+(X\oplus i))\bmod (10^9-1)$，表示将第 $x$ 个版本树上所有节点中的所有小朋友的第 $y$ 次祈愿获得的糖果数量乘上 $z$，得到第 $i$ 个版本树。 对于 C++，代码实现如下： ```cpp x = (X ^ i) % i, y = (X ^ i) % k + 1, z = (X + (X ^ i)) % 999999999; ```

由于输出文件过大无法上传，接下来我们将会以一种诡异的方式输出数据。 输出一行，表示第 $0\sim q$ 个版本树中快乐的节点数的异或和。

2 2 3 0
5

2

100 4 12 1919810
100

16

**样例 1 解释：** $a_{1,1,1}=2$，$a_{1,1,2}=3$，$a_{1,1,3}=4$，$a_{1,2,1}=3$，$a_{1,2,2}=5$，$a_{1,2,3}=7$，$a_{2,1,1}=5$，$a_{2,1,2}=6$，$a_{2,1,3}=7$，$a_{2,2,1}=6$，$a_{2,2,2}=8$，$a_{2,2,3}=10$。 对修改解密后为： ``` 0 2 1 0 3 2 0 1 3 0 2 4 0 3 5 ``` 对输出解密后为： ``` 2 2 2 0 2 2 ``` **数据范围：** 对于 $20\%$ 的数据，满足 $n\le 10^3$，$q\le 10^3$。 对于 $40\%$ 的数据，满足 $n\le 10^3$，$q\le 10^6$。 对于另外 $10\%$ 的数据，满足 $m=1$。 对于另外 $10\%$ 的数据，满足 $k=1$。 对于另外 $5\%$ 的数据，满足 $q=0$。 对于 $100\%$ 的数据，满足 $1\le n\le 10^5$，$1\le m\le 4$，$1\le k\le 12$，$0\le q\le 10^6$，$0\le a_{i,j,x}< 10^9$。对于第 $i$ 次修改，$0\le x<i$，$1\le y\le k$，$0\le z<10^9-1$。$0\le X\le 10^9$。