Boolean Expression

You are given a boolean expression made of 0, 1, the operators & (boolean AND), | (boolean OR), ^ (XOR, exclusive OR), and parentheses. A correct boolean expression is defined recursively. It is either a single character 0 or 1, or a boolean operation applied to two correct boolean expressions. For simplicity, every operation is wrapped in parentheses. The expression contains no spaces or other characters. For example, ((0|1)|0), (0&1), and 0 are correct, while 0|1, 0|1&1, and (0) are not. Compute the value of the expression. The expression changes over time. You are also given $m$ queries, and each query replaces the character at some position. After each query, compute the value of the expression again.

The first line contains a correct boolean expression $S$ with at most $800\,000$ characters. The second line contains an integer $m$ ($1 \le m \le 400\,000$), the number of queries. Each of the next $m$ lines contains an integer $p_i$ and a character $c_i$ separated by a space, meaning that the character at position $p_i$ is changed to $c_i$. The expression is guaranteed to remain correct after every query.

Print $m+1$ characters 0 or 1 on a single line. The first is the value of the original expression, and the next $m$ characters are the values after each query, in order.