H. 01 (Hard Version)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You have a binary string $$$S$$$, which is a string only containing 0s and 1s. Define $$$f(S)$$$ as the length of the shortest string you get after performing the operation to $$$S$$$:

  • Choose a substring $$$01$$$ and delete it from the string.

Michael is curious about the value of the function $$$f$$$ for some substrings of $$$S$$$. He challenges you to find the answer to some queries of $$$f(S[l,r])$$$. However, he finds that this is not interesting enough, so he might also flip a single bit $$$S_x$$$ of $$$S$$$: changing it from $$$0$$$ to $$$1$$$ or $$$1$$$ to $$$0$$$.

Here, $$$S[l,r]$$$ denotes the substring of $$$S$$$ that starts at the $$$l$$$-th character and ends at the $$$r$$$-th character. For example, if $$$S=abcde$$$, then $$$S[1,3] = abc,S[2,5]=bcde$$$.

Input

The first line contains a single binary string $$$S$$$ $$$(1\le |S|\le 2\times 10^5)$$$.

The second line contains a single integer $$$q$$$ $$$(1\le q\le 2\times 10^5)$$$, the number of operations.

The next $$$q$$$ line each contains an integer $$$k$$$ $$$(k=\{1,2\})$$$, the type of operation.

  • If $$$k=1$$$, the line follows an integer $$$x$$$ $$$(1\le x\le |S|)$$$, the place where Michael flips a bit. If $$$S_x=0$$$, then $$$S_x=1$$$ after this operation. Otherwise, it will be $$$0$$$.
  • If $$$k=2$$$, the line follows two integers $$$l,r$$$ $$$(1\le l\le r\le |S|)$$$, representing the position of Michael's substring of the current query.

Output

For each query with $$$k=2$$$, output a line with the answer $$$f(S[l,r])$$$.

Examples

Input
11001001
4
2 1 3
2 1 8
1 3
2 1 8
Output
3
4
4
Input
1011000110101010010
5
2 1 10
2 1 9
2 1 12
2 3 7
2 4 9
Output
4
3
4
5
2