1244 : 快速散列变换

Description

称一个 \(\mathcal{V}=\left\{0,1,\dots,2^{64}-1\right\}\) 上的封闭函数 \(f\) 是单轮散列函数，当且仅当它具有以下标准形式：

\[ f(X)=B \oplus \bigoplus_{j=1}^{m} \left((X\lll s_j)\circ_j A_j\right), \]

其中，

• \(A_j, B \in \mathcal{V}\)；
• \(0\le m\le 64\)，\(0\le s_j\le 63\) 且 \(s_j\) 互不相同；
• \(\oplus\) 为按位异或运算，\(\lll\) 为循环左移运算（在 \(\mathcal{V}\) 上的循环左移定义为对补齐至 \(64\) 位的无符号二进制表示进行循环左移），而 \(\circ_j\) 为按位或运算（记作 \(\lor\)）或按位与运算（记作 \(\land\)）中的一种。

给定 \(N\) 个单轮散列函数 \(f_1, f_2,\cdots,f_N\) 和 \(Q\) 次操作，操作有以下两种：

• 给出 \(l,r, x\)，求 \(f_r\left(\cdots\left(f_{l+1}\left(f_l(x)\right)\right)\cdots\right)\) 的值；

• 给出 \(l\)，修改 \(f_l\) 为新的单轮散列函数。

由于修改单轮散列函数会导致大量快速散列变换的计算结果失效，从实用性的角度考虑，保证这样的修改最多不超过 \(C\) 次。

Input

第一行为三个非负整数 \(N, Q, C\)，分别表示需要维护的单轮散列函数的数量、操作数量及需要修改单轮散列函数的操作数量。保证 \(1\le N, Q\le 20,000\)，\(0\le C\le 400\) 且 \(C<Q\)。

第二行至第 \((N+1)\) 行中，第 \((i+1)\) 行描述 \(f_i\) 的初始参数：

• 每行第一个非负整数 \(m_i\) 表示 \(f_i\) 的标准形式中的求异或和符号涉及的项数。保证 \(0\le m_i\le 64\)。

• 接下来依次输入 \(3m_i\) 个非负整数，其中第 \((3j-2)\)，\((3j-1)\) 和 \(3j\) 个整数分别为 \(s_{i,j}, o_{i,j}, A_{i,j}\)，分别表示求异或和符号的第 \(j\) 项中对 \(X\) 循环左移的位数，第 \(j\) 项的位运算 \(\circ_{i,j}\) 的类型（\(o_{i,j}=0\) 对应按位或运算，\(o_{i,j}=1\) 对应按位与运算）和第 \(j\) 项的位运算的常数项。保证 \(0\le s_{i,j}\le 63\) 且同一个单轮散列函数的 \(s_{i,j}\) 互不相同，\(0\le o_{i,j}\le 1\)，\(0\le A_{i,j}<2^{64}\)。

• 每行的最后为一个非负整数 \(B_i\)，表示标准形式中外层的常数项。保证 \(0\le B_i<2^{64}\)。

根据第二行至第 \((N+1)\) 行的输入，可得各 \(f_i\) 的初始表达式：

\[ f_i(X)=B_i \oplus \bigoplus_{j=1}^{m_i} \left((X\lll s_{i,j})\circ_{i,j} A_{i,j}\right). \]

第 \((N+1)\) 至第 \((N+Q+1)\) 行中，第 \((N+i+1)\) 行描述第 \(i\) 个操作。

• 每行的开头为一个非负整数 \(op\)，表示该操作的种类。

• 如果 \(op=0\)，则表示求快速散列变换的操作。并在此后跟随着 \(3\) 个非负整数 \(l,r,x\)，表示快速散列变换的起始位置、终止位置和初始值。保证 \(1\le l\le r\le N\)，\(0\le x<2^{64}\)。

• 如果 \(op=1\)，则表示修改某个单轮散列函数的操作。先输入一个整数 \(l\)，表示需要修改的单轮散列函数的编号。接下来依次输入若干个整数，描述修改后的 \(f_l\)。此处描述新的单轮散列函数的格式与描述各函数初始参数的格式相同。保证 \(1\le l\le N\)。

Output

输出包括 \((Q-C)\) 行。每行依次对应每个求快速散列变换的操作，输出一个非负整数表示求得的快速散列变换的结果。

Sample

3 5 1
1 4 0 0 51966
1 60 0 0 0
1 0 0 16 15
0 1 1 771
0 2 2 32368
0 3 3 0
1 2 2 0 0 15 61 1 4095 46681
0 1 3 2023

64206
2023
31
1112

Hint

【样例解释 #0】

\(3\) 个单轮散列函数的初始参数为：

• \(f_1(X)=(X\lll 4)\oplus 51966\)（\(51966\) 的十六进制表示为 0xCAFE）；

• \(f_2(X)=X\lll 60\)；

• \(f_3(X)=(X\lor 16)\oplus 15\)（\(16\) 和 \(15\) 的十六进制表示分别为 0x0010 和 0x000F）。

第 \(1\) 次操作是计算快速散列变换的操作。对 \(771\) （0x0303）进行快速散列变换的结果为 \(f_1(771)=(771 \lll 4)\oplus51996 = 64206\) （0xFACE）。

第 \(2\) 次操作是计算快速散列变换的操作。对 \(32368\)（0x7E70）进行快速散列变换的结果为 \(f_2(32368)=32368\lll 60=2023\)（0x07E7）。

第 \(3\) 次操作是计算快速散列变换的操作。对 \(0\)（0x0000）进行快速散列变换的结果为 \(f_3(0)=(0\lor 16)\oplus15=31\)（0x001F）。

第 \(4\) 次操作是修改 \(f_2\) 的操作。修改后，\(f_2(X)=(X\lor 15)\oplus((X\lll 61)\land 4095)\oplus46681\)（\(4095\) 和 \(46681\) 的十六进制表示分别为 0x0FFF 和 0xB659）。

第 \(5\) 次操作是计算快速散列变换的操作。对于初始值 \(2023\)（0x07E7），因为 \(f_1(2023)=46222\)（0xB48E），\(f_2(46222)=1095\)（0x0447），\(f_3(1095)=1112\)（0x0458），所以快速散列变换的结果为 \(1112\)。

【提示】

请注意输入输出效率对程序运行时间产生的影响。

在样例解释中，所有的十六进制表示均补齐至 \(4\) 个十六进制位，但这不代表输入的数不超过 \(65535\)。

【附件】

额外的样例

Source

Author

THU