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

密码门(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修改密码门的事件，好各有三组数据所有的操作符都是相同的.