Brackets Stack Query

A string $T$ is called a good bracket sequence if and only if it satisfies the following condition: * $T$ can be made into an empty string by repeating the following operation zero or more times: * Choose `()` contained in $T$ as a (contiguous) substring and remove it. For example, `()`, `(()())`, and the empty string are good bracket sequences, but `)()(` and `)))` are not good bracket sequences. There is a string $S$. Initially, $S$ is an empty string. Process $Q$ queries in the order they are given. After each query, determine whether $S$ is a good bracket sequence. There are two types of queries: * `1 c`: A character $c$ is given. $c$ is either `(` or `)`. Append $c$ to the end of $S$. * `2`: Remove the last character of $S$. It is guaranteed that $S$ is not an empty string at this time. ## Constraints * $1 \leq Q \leq 8 \times 10^5$ * $c$ in queries of the first type is `(` or `)`. * It is guaranteed that $S$ is not empty when a query of the second type is given. * $Q$ is an integer. ## Input The input is given from Standard Input in the following format, where $\mathrm{query}_i$ denotes the $i$\-th query. $Q$ $\mathrm{query}_1$ $\mathrm{query}_2$ $\vdots$ $\mathrm{query}_Q$ Each query is given in one of the following two formats: $1$ $c$ $2$ [samples]