Little R and his roommate Little B are playing a game in their dorm. They play a total of $n$ rounds, and the result of each round is either a win for Little R or a win for Little B.

The probability that Little R wins the first round is $p_1$, and the probability that Little B wins is $1-p_1$. For every round after the first, the probability of Little R winning depends on whether he won the previous round.

Specifically:

1. If Little R won round $i-1$ ($1 < i \le n$), the probability that Little R wins round $i$ is $p_i$, and the probability that Little B wins is $1-p_i$.
2. If Little B won round $i-1$ ($1 < i \le n$), the probability that Little R wins round $i$ is $q_i$, and the probability that Little B wins is $1-q_i$.

Little D often comes to watch them play, so he knows the results of some rounds. He wants to know the expected total number of rounds Little R wins, given the information he knows.

Little D has a poor memory; sometimes he recalls the result of a round and adds it to his known information, and sometimes he forgets a result and removes it from his known information. Your task is: every time Little D adds or removes a piece of information, calculate the expected total number of rounds Little R wins based on his current knowledge.

Note that if Little D forgets a result and later remembers it again, the remembered result is not necessarily the same as the previous one. You do not need to worry about whether Little D's memory matches reality; you only need to calculate the answer based on his current memory.

Input

The first line contains two positive integers $n, m$ and a string $type$. This indicates that Little R and Little B played $n$ rounds, Little D performed $m$ operations to modify his known information, and the data type is $type$. The $type$ string is provided to help you obtain partial points; you may not need to use this input. Its specific meaning is explained in the Constraints section.

The next $n$ lines: the first line contains a real number $p_1$, representing the probability that Little R wins the first round. Each subsequent line $i$ ($1 < i \le n$) contains two real numbers $p_i, q_i$. $p_i$ is the probability that Little R wins round $i$ given that he won round $i-1$, and $q_i$ is the probability that Little R wins round $i$ given that Little B won round $i-1$.

The next $m$ lines each describe a change in Little D's known information. The operations are of two types:

1. add i c: Little D recalls the result of round $i$ and adds it to his known information. If $c=0$, Little B won round $i$; if $c=1$, Little R won round $i$. It is guaranteed that $i$ and $c$ are integers with $1 \le i \le n$ and $0 \le c \le 1$. If this is not the first operation, it is guaranteed that the result of round $i$ is not already in the known information after the previous operation.
2. del i: Little D forgets the result of round $i$ and removes it from his known information. It is guaranteed that $i$ is an integer with $1 \le i \le n$, and that the result of round $i$ is currently in the known information after the previous operation.

Output

For each operation, output a single real number representing the expected total number of rounds Little R wins, given the current known information.

Examples

Input 1

3 3 A
0.3
0.5 0.2
0.9 0.8
add 1 1
add 3 0
del 1

Output 1

2.350000
1.333333
0.432749

Note 1

Using Bayes' theorem:

First Query

$$p(x_2=1|x_1=1)=0.5,p(x_3=1|x_1=1)=0.5*0.9+0.5*0.8=0.85,E(x_1+x_2+x_3|x_1=1)=0.5+0.85+1=2.35$$

Second Query

$$p(x_2=1|x_1=1,x_3=0)=\frac{p(x_3=0|x_1=1,x_2=1)p(x_2=1|x_3=0)}{p(x_3=0|x_1=1)} \approx 0.333,E(x_1+x_2+x_3|x_1=1,x_3=0) \approx 1.333$$

Third Query

$$p(x_2=1|x_3=0)=\frac{p(x_3=0|x_2=1)p(x_2=1)}{p(x_3=0)}$$

Where

$$p(x_3=0|x_2=1)=0.1,p(x_2=1)=0.3*0.5+0.7*0.2=0.29,p(x_3=0)=0.29*0.1+0.71*0.2=0.171$$

So

$$p(x_2=1|x_3=0)=0.1*0.29/0.171 \approx 0.16959$$

$$p(x_1=1|x_3=0)=\frac{p(x_3=0|x_1=1)p(x_1=1)}{p(x_3=0)}$$

Where

$$p(x_3=0|x_1=1)=0.5*0.1+0.5*0.2=0.15,p(x_1=1)=0.3,p(x_3=0)=0.171$$

So

$$p(x_1=1|x_3=0)=0.15*0.3/0.171 \approx 0.26316$$

$$E(x_1+x_2+x_3|x_3=0) \approx 0.43275$$

Constraints

For 100% of the data, $1 \le n \le 200000, 1 \le m \le 200000, 0 < p_i, q_i < 1$.

For 100% of the data, the input retains at most four decimal places.

There are 20 test cases in total, each worth 5 points. The specific constraints for each test case are as follows:

Meaning of data types:

A: No restrictions. B: $\forall i > 1, |p_i-q_i| > 0.999$. C: At any given time, Little D has at most 1 piece of known information. D: At any given time, Little D has at most 5 pieces of known information.

Mathematical Background

You may need the following formulas:

1. Calculation of conditional probability: $$p(A|B)=\frac{p(AB)}{p(B)}$$

2. Bayes' theorem: $$p(A|B)=\frac{p(B|A)p(A)}{p(B)}$$

3. Law of total probability: If a random variable $x$ has $k$ values $x_1, x_2, \ldots, x_k$, then: $$p(A)=\sum_{i=1}^k p(A|x=x_i)p(x=x_i)$$

Note

In this problem, if you wish to obtain full marks, you may need to consider the errors introduced by floating-point operations. Using only addition and multiplication will not introduce significant errors, but please be cautious with subtraction and division.

1. Subtracting two numbers that are close in value can introduce very large relative errors.
2. If the determinant of a matrix is very small, solving for the inverse of that matrix can lead to significant errors.

Of course, if your algorithm is mathematically correct but does not account for floating-point errors, you may still be able to obtain partial marks.