SP3981 MBRACKET - Shortest Regular Bracket

[English](/problems/MBRACKET/en/) [Vietnamese](/problems/MBRACKET/vn/) ``` Lets observe sequences made only of round and square brackets, i.e. characters '( ) [ ]'. A sequence of brackets is regular if it satisfies this inductive definition: 1. '( )' and '[ ]' are regular sequences 2. If A is regular, then (A) and [A] are regular sequences 3. If A and B are regular, then AB is regular sequence. For example '( ) ( ) [ ]', '( [ ] ) [ ( ) ]' and '[ ( ( ) ) ] [ ]' are regular, while '(', '] [', '[ ( ]' and '( [ ) ]' are not regular. The sequence of brackets is given. In every step, one bracket is inserted at the beginning or at the end of the sequence (round or square, left or right). Write a program that will, after each step, determine the length of the shortest regular subsequence of consecutive characters that contains the bracket added in that step. ```

``` First line contains initial sequence of brackets, whose length is at most 100,000 characters. Next line contains integer N, 1 ```

``` In each of N lines, you should write the length of subsequence after that step. If there is no such subsequence, write number 0. ```