令 V={0,1,…,264−1}。定义 V 上的函数 f 是一个单轮散列函数,当且仅当它具有下列标准形式:
$$f(X)=B\oplus\bigoplus_{j=1}^{m}\bigl((\operatorname{ROL}_{64}(X,s_j))\circ_j A_j\bigr).$$
其中 Aj,B∈V,0≤m≤64,0≤sj≤63,同一个函数中的所有 sj 两两不同;⊕ 表示按位异或,∘j 是按位或或按位与。ROL64(X,s) 表示将 X 补足为 64 位无符号二进制表示后循环左移 s 位:从最高位移出的位重新进入最低位。移位 0 位时保持不变。异或项为空时其值为 0,因此 m=0 时 f(X)=B。
给定 N 个单轮散列函数 f1,f2,…,fN,以及 Q 次操作,操作有以下两类:
- 给定 l,r,x,计算 fr(⋯(fl+1(fl(x)))⋯),即按下标从 l 到 r 依次应用函数。
- 给定 l,将 fl 修改为一个新的单轮散列函数。修改对其后的操作持续生效。
修改散列函数会使许多预计算结果失效,因此保证第二类操作最多 C 次。
输入格式
第一行包含三个非负整数 N,Q,C。保证 1≤N,Q≤20000,0≤C≤400,且 C<Q。
接下来 N 行,第 i 行描述初始函数 fi。每行依次包含:
- 一个非负整数 m,表示异或项的个数,0≤m≤64。
- 接下来 3m 个非负整数,按 s1,o1,A1,s2,o2,A2,…,sm,om,Am 的顺序给出。其中 0≤sj≤63,同一个函数中的移位量两两不同;oj=0 表示按位或,oj=1 表示按位与;0≤Aj<264。
- 最后一个非负整数 B,0≤B<264。
再接下来 Q 行,每行描述一次操作:
0 l r x:输出从 fl 到 fr 的复合变换作用于 x 的结果。保证 1≤l≤r≤N,0≤x<264。
1 l m s1 o1 A1 ... sm om Am B:将 fl 替换为此行给出的新函数,函数参数的格式和限制与初始函数相同。保证 1≤l≤N。
第二类操作不超过 C 次。所有数均使用十进制表示。输入只有一组数据。
输出格式
对每次第一类操作,单独输出一行一个十进制整数,表示答案。答案属于 V。
样例
输入:
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
样例说明
初始的三个函数分别为:
$$f_1(X)=\operatorname{ROL}_{64}(X,4)\oplus51966,\qquad
f_2(X)=\operatorname{ROL}_{64}(X,60),\qquad
f_3(X)=(X\mathbin{\vert}16)\oplus15.$$
- 第一次操作:f1(771)=64206。相应十六进制数为 771=0x0303、51966=0xCAFE、64206=0xFACE。
- 第二次操作:f2(32368)=2023,其中 32368=0x7E70、2023=0x07E7。
- 第三次操作:f3(0)=31=0x001F,其中 16=0x0010、15=0x000F。
- 第四次操作后,$f_2(X)=(X\mathbin{\vert}15)\oplus(\operatorname{ROL}_{64}(X,61)\mathbin{\&}4095)\oplus46681$,其中 4095=0x0FFF、46681=0xB659。
- 第五次操作中,f1(2023)=46222=0xB48E,修改后的 f2(46222)=1095=0x0447,f3(1095)=1112=0x0458,故输出 1112。
请注意输入输出效率。样例说明中十六进制数补为四位只是为了展示,不表示输入数不会超过 65535;实际数值可以达到 264−1。