불 식

주어진 식은 0, 1, 연산자 &(불 AND), |(불 OR), ^(XOR, 배타적 OR), 그리고 괄호로만 이루어진다. 올바른 불 식은 재귀적으로 정의된다. 식이 문자 0 또는 1 하나이거나, 올바른 불 식 두 개에 불 연산 하나를 적용한 것이면 올바르다. 간단하게 하려고 모든 연산은 괄호로 감싼다. 식에는 공백이나 위에 나온 문자 외의 다른 문자가 없다. 예를 들어 ((0|1)|0), (0&1), 0은 올바른 식이고, 0|1, 0|1&1, (0)은 올바르지 않다. 식의 값을 구하라. 이 식은 질의에 따라 바뀐다. $m$개의 질의가 주어지며, 각 질의는 어떤 위치의 문자를 바꾼다. 매 질의 후의 식 값을 구하라.

첫 줄에 최대 $800\,000$ 문자의 올바른 불 식 $S$가 주어진다. 둘째 줄에는 질의의 개수 $m$ ($1 \le m \le 400\,000$)이 주어진다. 이어지는 $m$개의 줄에는 정수 $p_i$와 문자 $c_i$가 공백으로 구분되어 주어지며, 이는 위치 $p_i$의 문자를 $c_i$로 바꾼다는 뜻이다. 모든 질의 후에도 식이 올바른 상태를 유지함이 보장된다.

한 줄에 0 또는 1 문자 $m+1$개를 출력한다. 첫 문자는 원래 식의 값이고, 이어지는 $m$개 문자는 질의를 순서대로 적용한 뒤의 식 값이다.