该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

密码门(cipher)

题目描述

为了防止秘密情报泄露，Kiana决定在基地内加装$n$道密码门，每道密码门可以对输入的数字做一定计算，并将结果输出给下一道密码门作为输入。只要Kiana对比入口处输入的数字经过所有密码门后的结果，就可以判断出来者是否掌握真正的密码。

具体而言，第$i$道密码门有一个操作符$OP_i$和一个参数$B_i$，其中操作符分为三种：AND、OR和XOR，分别表示该密码门会将输入的数字与$B_i$进行按位与、按位或、按位异或后进行输出。按位与对应C++中的$'\&'$运算符，按位或对应C++中的$'|'$运算符，按位异或对应C++中的$'\^{}'$运算符，你可以分别用表达式$'a\&b'$、$'a|b'$和$'a\^{}b'$计算两个数$a$和$b$进行按位与、按位或、按位异或运算的结果。

为进一步保证安全，在某些时刻，Kiana还可能修改某些密码门的操作符和参数。基地中按时间顺序共发生了$m$个事件，每个事件可能为有人在基地门口输入了一个数字，或者Kiana修改了某一道密码门的操作符和参数。

对于每个输入数字事件，虽然密码门可以自动计算出结果来，但Kiana还是希望提前知道该数字依次通过所有密码门后的结果是什么，以便针对特殊情况做出预警。由于Kiana自己不会算，所以希望你能够帮助她。

输入输出格式

输入格式

第一行包含两个正整数$n$和$m$，分别表示密码门的数量与发生的事件数。

接下来$n$行，第$i$行包含一个字符串$OP_i$和一个正整数$B_i$，分别表示初始时第$i$道密码门的操作符和参数。

接下来$m$行，每行首先包含一个正整数$type$，若$type=1$，则后面跟一个正整数$X$，表示有人在门口输入了数字$X$，你需要计算$X$依次通过所有密码门后的结果；若$type=2$，则后面跟一个正整数$id$、一个字符串$OP'$和一个正整数$B'$，表示Kiana将第$id$道密码门的操作符改为了$OP'$，参数改为了$B'$。

数据保证输入中的字符串均为'AND'、'OR'或'XOR'中的一种，其分别对应这道密码门进行按位与、按位或、按位异或运算。

输出格式

对于每个输入数字事件，输出一行一个正整数，表示基地门口输入的数字依次通过所有密码门后输出的结果。

输入输出样例

输入样例#1：

3 3
XOR 11
AND 7
OR 17
1 13
2 2 AND 15
1 5

输出样例#1：

23
31

输入样例#2：

cipher2.in

输出样例#2：

cipher2.ans

样例解释

Kiana一共加装了$3$道密码门，初始时密码门的操作符和参数依次为$XOR\,11$、$AND\,7$和$OR\,17$，按时间顺序发生了$3$个事件如下：

• 有人在门口输入了数字$13$，而$13\,XOR\,11=15$、$15\,AND\,7=7$、$7\,OR\,17=23$，故最终密码门输出的结果为$23$

• Kiana将第$2$道密码门的参数改为$AND\,15$

• 有人在门口输入了数字$5$，而$5\,XOR\,11=14$、$14\,AND\,15=14$、$14\,OR\,17=31$，故最终密码门输出的结果为$31$。

数据范围

对于$20\%$的数据，保证$1\leq n,m\leq 2000$。

对于$60\%$的数据，保证$1\leq n,m\leq 20000$。

对于$100\%$的数据，保证$1\leq n,m\leq 2\times 10^5,1\leq type\leq 2,1\leq B_i,B',X\leq 1000,1\leq id\leq n$。

在后两档数据中，各有三组数据没有发生过Kiana修改密码门的事件，好各有三组数据所有的操作符都是相同的.