A regular bracket sequence is a sequence of '$($' and '$)$' characters defined as follows:

• The empty string (without any characters) is a regular bracket sequence.
• If $A$ is a regular bracket sequence, then $(A)$ is also considered a regular sequence.
• If $A$ and $B$ are regular bracket sequences, then $AB$ is also considered as a regular bracket sequence.

For a string $S$ that consists of only '$($' and '$)$' characters, consider a sequence of $M$ operations that are of one of the following types:

• $C$ $i$: If the character $S$$_{i}$ is an opening bracket '$($' , then it is replaced by a closing bracket '$)$'. Similarly, the '$)$' character is replaced by the '$($' character.
• $Q$ $i$: Determine the maximum length $K$ of the regular bracket sequence starting at index $i$ of the string. Formally, the string $S_{i}$ $S_{i+1}$... $S_{i+K-1}$ should be a regular bracket sequence, where $K$ is maximized. If there is no regular bracket sequence starting at index $i$, then print $0$.

Input format

• First line: String $S$
• Next line: $M$ representing the number of queries
• Next $M$ lines: A query of the following types:
  • $C$ $i$
  • $Q$ $i$

Output format

For the query of the type $Q$ , print the length of the longest regular bracket sequence starting at index $i$.

Input Constraints

$1 \le |S| \le 2 \times 10^5$

$1 \le M \le 2 \times 10^5$

$1 \le i_{query} \le N$