비트 연산 식

야니카는 최근 비트 연산 AND, OR, XOR를 배웠고, 이 연산으로 식을 만들어 그 값을 계산하려고 한다.

식의 맨 앞에는 숫자 $0$이 쓰여 있다. 그 뒤에 $N$개의 연산이 이어지며, 각 연산은 배운 비트 연산 중 하나와 정수 하나로 이루어진다. 예를 들어 $N = 6$일 때 다음과 같은 식이 된다.

0 XOR 2 AND 5 OR 9 XOR 0 AND 8 OR 10

식의 값은 항상 왼쪽에서 오른쪽으로 계산한다. 이를 괄호로 나타내면 다음과 같다.

((((((0 XOR 2) AND 5) OR 9) XOR 0) AND 8) OR 10)

야니카는 식의 연산을 하나씩 바꾸려고 한다. 예를 들어 OR 9를 XOR 13으로 바꿀 수 있다. 야니카는 이런 변경을 $Q$번 연속으로 하며, 변경할 때마다 새 식의 값을 알고 싶어 한다.

첫 줄에는 연산의 개수 $N$ ($1 \le N \le 10^5$)과 변경 횟수 $Q$ ($1 \le Q \le 10^5$)가 주어진다.

다음 $N$개 줄에는 처음 식의 각 연산이 주어진다. 각 줄에는 연산 이름 AND, OR, XOR 중 하나와 정수 $X$ ($0 \le X \le 10^9$)가 주어진다.

다음 $Q$개 줄에는 각 변경이 주어진다. 각 줄에는 바꿀 연산의 순서 번호 $I$ ($1 \le I \le N$), 새 연산 이름 AND, OR, XOR 중 하나, 새 정수 $X$ ($0 \le X \le 10^9$)가 주어진다.

각 변경 후 식의 값을 한 줄에 하나씩 정수로 출력한다.

AND(논리 곱)는 두 참거짓 값에 대한 연산이며, 두 값이 모두 참일 때만 참이고 그 밖의 경우에는 거짓이다. OR(논리 합)은 두 값이 모두 거짓일 때만 거짓이고 그 밖의 경우에는 참이다. XOR(배타적 논리 합)은 두 값 중 정확히 하나가 참일 때 참이고 그 밖의 경우에는 거짓이다.

이 연산을 정수에 적용할 때는 두 수를 이진수로 나타내고, 각 비트를 참($1$)이나 거짓($0$)으로 본다. 같은 자리의 비트끼리 연산한 뒤, 결과 비트들로 새 이진수를 만든다.

예를 들어 $5$의 이진수는 $0101_2$이고 $12$의 이진수는 $1100_2$이다. $0101_2$ XOR $1100_2$는 낮은 자리부터 1 XOR 0 = 1, 0 XOR 0 = 0, 1 XOR 1 = 0, 0 XOR 1 = 1을 계산하므로 $1001_2$, 즉 $9$가 된다. 따라서 $5$ XOR $12 = 9$이다.