C. K Flips
time limit per test
2.5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output
if't be true thee wast mad, flip some tables
— Paulo, Palou's Advice to Ahmad

Paulo was teaching Ahmad that if he was ever mad he should just flip some tables, but Paulo did not listen to his own advice, and now he is in prison, so Ahmad is MAD!

You're given a binary string $$$S$$$, the $$$i_{th}$$$ character is the state of the $$$i_{th}$$$ table either $$$1$$$ flipped, or $$$0$$$ not flipped.

Every time Ahmad wants to flip some tables, he will chose some pair $$$(l, r)$$$ uniformly at random from all the pairs such that $$$(1 \leq l \leq r \leq |S|)$$$, and flip every table $$$i$$$ such that $$$(l \leq i \leq r)$$$.

You have to answer $$$Q$$$ queries:

  • $$$1$$$ $$$i$$$: flip the $$$i_{th}$$$ table.
  • $$$2$$$ $$$k$$$: Ahmad will flip some tables $$$k$$$ $$$(k \leq 200)$$$ times, what is the expected number of tables that are flipped at the end of $$$k$$$ flips?

Note: when Ahmad flips some tables, every time he flips he will choose $$$(l, r)$$$ again.

Note: only query of type $$$1$$$ will change the string, meaning Ahmad's flips will not have any effect on the string.

Input

The first line contains the string $$$S$$$ $$$(1 \leq |S| \leq 10^5)$$$ – the binary string.

The second line contains the integer $$$Q$$$ $$$(1 \leq Q \leq 10^5)$$$ – The number queries.

The next $$$Q$$$ lines contains two integers, either $$$1$$$ $$$i$$$ $$$(1 \leq i \leq |S|)$$$, or $$$2$$$ $$$k$$$ $$$(1 \leq k \leq 200)$$$.

Output

For every query of type 2 print a decimal number, the expected number of tables that will be flipped.

Your answer is considered correct if its absolute or relative error doesn't exceed $$$10^{-6}$$$. Namely, if your answer is $$$a$$$, and the jury's answer is $$$b$$$, then your answer is accepted, if $$$\frac{|a - b|}{max(1, |b|)} \leq 10^{-6}$$$.

Examples
Input
1010
3
2 1
2 2
2 3
Output
2.000000
2.000000
2.000000
Input
00110
6
2 2
1 1
2 2
1 2
2 2
2 10
Output
2.408889
2.520000
2.524444
2.500000
Input
101
6
2 1
2 2
2 3
1 3
2 1
2 2
Output
1.666667
1.444444
1.518519
1.666667
1.444444