Balanced Bracket Segment

Time limit1sMemory limit128 MB

Summary

Maintain a dynamic string under prefix/suffix bracket insertions and after each insertion report the shortest valid contiguous bracket substring covering the new character.

Level: Hard8 of 10
Topics: Stack, String matching, Implementation
Solved: No attempts yet

Problem

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

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

() and [] are regular sequences.
If A is a regular sequence, then (A) and [A] are also regular sequences.
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.

Input

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 (, ), [, ].

Output

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

Examples3

Example 1
Input
```
(
1
1 )
```
Expected output
```
2
```
Example 2
Input
```
(]
3
1 )
0 )
0 (
```
Expected output
```
0
0
2
```
Example 3
Input
```
[])
3
0 )
0 (
0 (
```
Expected output
```
0
2
6
```