跳蚤国王成功夺回了管理员权限，并剥夺了 Skip 蚤的权限，让其在 UOJ 上禁赛三年，且所在省的跳蚤 Rating 强制扣$100$。

跳蚤国王在检查题库时，发现 Skip 蚤获得权限期间，一位热爱线段树的 Picks 往 OJ 上传了一道没有 std 的题目。

因为之前的行为引起了民愤，出题人 Picks 拒绝向跳蚤国王透露这题的解法。正巧跳蚤国王准备筹办的 ULR #2 缺一道题，你能帮助跳蚤国王解开这道题以完成 ULR 的筹备吗？

给定一个长度为 $n$ 的操作序列。操作有 4 种：

1. | x：将非负整数 $v$ 变为 $v\mathrm{bitor}x$，其中 $\mathrm{bitor}$ 为按位或操作；
2. & x：将非负整数 $v$ 变为 $v\mathrm{bitand}x$，其中 $\mathrm{bitand}$ 为按位与操作；
3. ^ x：将非负整数 $v$ 变为 $v\mathrm{bitxor}x$，其中 $\mathrm{bitxor}$ 为按位异或操作；
4. + x：将非负整数 $v$ 变为 $(v+x)mod{2}^{32}$。这一种操作保证 $x=1$。

所有操作的 $x$ 均为输入给定的非负整数，每一个操作的 $x$ 并不一定相同。操作从 $0$ 开始编号。

给定 $q$ 次询问，每次给出整数 $v,l,r,t$，求对数 $v$ 依次进行操作序列中区间 $[l,r]$ 中的操作后写成二进制形式，从低到高第 $t+1$ 个二进制位（即表示 $2^t$ 的位）的值，容易发现每组询问的答案只有可能是 $0$ 或 $1$。

本题部分子任务强制在线，详见输入格式和限制与约定部分。

输入格式

第一行三个整数 $n,q,op$ 表示操作序列长度、询问个数、询问解密参数。

接下来 $n$ 行依次描述操作序列中的每个元素。每行一个字符 $c$ 表示操作类型，后接一个整数 $x$ 表示操作参数。对于 + 操作保证 $x=1$。

接下来 $q$ 行每行四个整数 $v^{\prime },l^{\prime },r^{\prime },t^{\prime }$ 表示一组询问。注意询问进行了加密，解密方法如下：

• 设需要解密的询问为第 $t$ 组询问，$an{s}_i$ 表示第 $i$ 组询问的答案，询问从 $0$ 开始编号；
• 计算 $\mathrm{key}=op\times (\sum _{i=0}^{t-1}{2}^{i}an{s}_i)\mathrm{mod}998244353$；
• 则对应询问的真实参数如下： $$\begin{array}{rl}v& =(v^{\prime }+\mathrm{key})mod{2}^{32}\\ l& =min\{(l^{\prime }\mathrm{bitxor}\mathrm{key})modn,(r^{\prime }\mathrm{bitxor}\mathrm{key})modn\}\\ r& =max\{(l^{\prime }\mathrm{bitxor}\mathrm{key})modn,(r^{\prime }\mathrm{bitxor}\mathrm{key})modn\}\\ t& =(t^{\prime }\mathrm{bitxor}\mathrm{key})mod32\end{array}$$

注意解密过程中 $v$ 的计算方式与其他三者不同。注意无论询问是否强制在线都需要进行询问解密。

输出格式

一行一个长度为 $q$ 的 01 字符串，其中第 $i$ 个字符表示第 $i$ 组询问的答案。

样例一

input

6 6 0
^ 17
+ 1
^ 28
| 6
& 29
+ 1
3 0 2 1
8 1 5 3
7 1 4 0
12 0 4 2
31 0 2 1
50 1 2 0

output

100111

explanation

• 第一个询问中有 $3\stackrel{\mathrm{bitxor}17}{\to }18\stackrel{+1}{\to }19\stackrel{\mathrm{bitxor}28}{\to }15=(1111{)}_2$，其表示 $2^1$ 的二进制位，即从右往左数第 $2$ 个二进制位的值为 $1$，故第一个询问答案为 $1$；
• 第二个询问中有 $8\stackrel{+1}{\to }9\stackrel{\mathrm{bitxor}28}{\to }21\stackrel{\mathrm{bitor}6}{\to }23\stackrel{\mathrm{bitand}29}{\to }21\stackrel{+1}{\to }22=(10110{)}_2$，其表示 $2^3$ 的二进制位，即从右往左数第 $4$ 个二进制位的值为 $0$，故第二个询问答案为 $0$。

样例二

input

6 6 1
^ 17
+ 1
^ 28
| 6
& 29
+ 1
3 13674554 3172638 395059201
7 6992286 3863695438 3302730626
6 122315987 1653449004 2270895617
11 277356193 306830369 65457603
22 2313889149 858796667 36414120
25 4135467483 3048814434 3407639193

output

100111

explanation

该样例解密后即为样例一。

样例三

见附加文件中 ex_sequence3.in 与 ex_sequence3.ans，该组样例满足子任务 $1$ 的性质。

样例四

见附加文件中 ex_sequence4.in 与 ex_sequence4.ans，该组样例满足子任务 $3$ 的性质。

样例五

见附加文件中 ex_sequence5.in 与 ex_sequence5.ans，该组样例满足子任务 $6$ 的性质。

限制与约定

对于 $100\mathrm{\%}$ 的数据，$1\le n\le {10}^5,1\le q\le 6\times {10}^5,0\le op\le 1,0\le x,v^{\prime },l^{\prime },r^{\prime },t^{\prime }<2^{32}$。保证当操作为 + 操作时 $x=1$。

本题数据中读入的最大文件大小约为 $\mathtt{\text{30MB}}$，请注意算法常数如读入速度对运行时间带来的影响。

时间限制：$\mathtt{\text{2s}}$

空间限制：$\mathtt{\text{512MB}}$

下载

样例数据下载