Balanced Bracket Segment

A string consists only of the four bracket characters ()[].

A bracket sequence is regular if it can be built by the following rules.

1. () and [] are regular sequences.
2. If A is a regular sequence, then (A) and [A] are also regular sequences.
3. If A and B are regular sequences, then AB is also a regular sequence.

An initial bracket sequence is given. Then, in each step, one bracket is inserted either at the beginning or at the end of the current string.

After each step, find the minimum length of a contiguous substring that is a regular bracket sequence and contains the bracket inserted in that step.

The first line contains the initial bracket sequence. Its length is at most 100,000.

The second line contains an integer N, the number of steps. (1 ≤ N ≤ 100,000)

Each of the next N lines contains an integer A and a character C, separated by one space. If A is 0, insert C at the beginning of the current string. If A is 1, insert C at the end. The character C is one of (, ), [, ].

For each step, output one line containing the answer. If no regular contiguous substring contains the newly inserted bracket, output 0.