Mismatch Suffix Prefix Count

You are given a string ( S ) of length ( n ). There are ( m ) operations (with ( m \le n )). You also have an initially empty string ( T ). There are two kinds of operations:

1. Append a character to the end of ( T ).
2. Prepend a character to the beginning of ( T ).

After each operation, you need to output the number of integers ( l ) (with ( 1 \le l \le |T| )) such that for every ( i ) with ( 1 \le i \le l ), the following condition holds:

[ T_{|T|-l+i} \ne S_{i} ]

Note: The string indices are 1-based and (|T|) denotes the length of ( T ).

inputFormat

The first line contains the string ( S ).
The second line contains an integer ( m ), the number of operations.
Each of the next ( m ) lines contains an operation in the format:

• An integer ( type ) (either 1 or 2) and a space followed by a character ( c ).

If ( type = 1 ), append character ( c ) to the end of ( T ). If ( type = 2 ), prepend character ( c ) to the beginning of ( T ).

outputFormat

After each operation, output a single integer on a new line: the count of ( l ) ((1 \le l \le |T|)) satisfying that for every ( i ) from 1 to ( l ), ( T_{|T|-l+i} \ne S_{i} ).

sample

abc
3
1 a
1 b
1 c

0
1
2