Problem Statement

A string $T$ is called a good barred bracket sequence if $T$ satisfies the following condition.

• $T$ can be turned into the empty string by repeating the following operation 0 or more times.
  • Choose an occurrence of (|) as a (contiguous) substring and remove it.

For example, (|), ((|)|(|)), and the empty string are good barred bracket sequences, but )|( and )||()) are not.

There is a string $S$. $S$ is initially the empty string. Process the $Q$ queries described below in the given order. Then, immediately after each query, determine whether $S$ is a good barred bracket sequence. There are 2 types of queries.

• 1 c: A character $c$ is given. $c$ is (, |, or ). Append $c$ to the end of $S$.
• 2: Delete the last character of $S$. Here, it is guaranteed that $S$ is not the empty string.

Constraints

• $1≤Q≤8 \times 10^5$
• In a query of the 1st type, $c$ is (, |, or )
• $S$ is not empty when a query of the 2nd type is given

Input

$Q$
$\text{query}_1$
...
$\text{query}_Q$

Here, $\text{query}_i$ represents the $i$-th query and is given in one of the following formats.

Output

Print $Q$ lines. On the $i$-th line, print Yes if $S$ immediately after processing the $i$-th query is a good barred bracket sequence, and No otherwise.

Sample

5
1 (
1 |
1 )
2
1 |

No
No
Yes
No
No

2
1 (
1 )

No
No