|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|3 초||512 MB||4||2||2||50.000%|
You are given a boolean expression, consisting of <<
1>>, operations <<
&>> (boolean "AND"), <<
|>> (boolean "OR"), <<
^>> (<<XOR>>, boolean "exclusive OR"), and parentheses. A correct boolean expression can be defined recursively: an expression is correct, if it is either equal to one character <<
0>> or <<
1>>, or it is an application of some boolean operation to two correct boolean expressions. For simplicity, every application of a boolean operation is put into parentheses. The given expression does not contain spaces or any other characters except the ones described above. For instance, <<
(0&1)>> and <<
0>> are correct expressions, and <<
0|1&1>> and <<
(0)>> are not.
Calculate the result of this expression. By the way, the expression is changing! You are also given $m$ queries to change a character at some position. Calculate the value of the given expression after each query.
First line contains string $S$, a correct boolean expression with at most $800\,000$ characters.
Next line contains a single integer $m$ ($1 \le m \le 400\,000$) --- number of queries. Then, $m$ lines follow. Each line contains an integer and a character
$p_i$ $c_i$, meaning that you should change a character at position $p_i$ to $c_i$. It's guaranteed that the expression remains correct after every query.
Output $m+1$ characters <<
0>> or <<
1>> on a single line. First character should be equal to the value of the original expression. Next $m$ characters should be equal to the value of the expression after each query.
$|S| \le 5$, $m \le 10$
$|S| \le 200$, $m \le 200$
$|S| \le 2\,000$, $m \le 2\,000$
$|S| \le 200\,000$, $m \le 100\,000$
$|S| \le 800\,000$, $m \le 400\,000$
((1&1)^(0|1)) 3 11 0 7 | 5 0