Background

Numbers and mathematical laws govern the world.

The operation of machines,

The growth and decline of life,

The progression of the universe,

These mysterious and beautiful processes can all be expressed in the language of mathematics.

This confirms an old saying:

"Master mathematics, physics, and chemistry, and you can travel the world without fear."

Description

Little R, a poor student, is tortured by university mathematics courses to the point where he cannot take care of himself; his calculus grade was once the lowest among all the courses he took in the classroom. However, one of his roommates, surnamed Chen, can easily get full marks in math exams. To improve his math grades, one night (while he was sleeping), he came to the Kingdom of Mathematics.

In the Kingdom of Mathematics, everyone's IQ can be represented by a real number in $[0, 1]$. There are $n$ cities in the kingdom, numbered from $0$ to $n-1$, connected by several magic bridges. At the center of each city is a magic ball, and each magic ball contains a math problem. After completing the math problem, everyone receives a score in the interval $[0, 1]$. A problem can be represented by a function $f(x)$ that maps $[0, 1]$ to $[0, 1]$. If a person's IQ is $x$, they will receive a score of $f(x)$ after completing the problem. The function $f$ has three forms:

1. Sine function $sin(a x + b)\ (a \in [0,1], b \in [0,\pi],a+b\in[0,\pi])$
2. Exponential function $e^{ax+b}\ (a\in [-1,1], b\in [-2,0], a+b\in [-2,0])$
3. Linear function $ax + b\ (a\in [-1,1],b\in[0,1],a+b\in [0,1])$

The magic bridges in the Kingdom of Mathematics change; sometimes a magic bridge disappears, and sometimes a magic bridge appears. However, at any given time, there is at most one simple path connecting any two cities (i.e., all cities form a forest). Initially, there are no magic bridges in the Kingdom of Mathematics.

Lagrange, the King of the Kingdom of Mathematics, is happy to teach Little R mathematics, provided that Little R answers the King's questions first. These questions have the same form: what is the sum of scores for a person with IQ $x$ traveling from city $u$ to city $v$ (i.e., passing through all cities on the path from $u$ to $v$, including $u$ and $v$) after completing all the math problems in those cities?

Input

The input is read from standard input.

The first line contains two positive integers $n, m$ and a string $type$. This indicates that there are $n$ cities in the Kingdom of Mathematics, $m$ events occur, 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 Constraints.

The next $n$ lines each describe the function in the magic ball of city $i$ initially. A magic is represented by an integer $f$ for the function type and two real numbers $a, b$ for the function parameters. If:

1. $f=1$, the function is $f(x)=sin(ax+b)(a \in [0,1], b \in [0,\pi],a+b\in[0,\pi])$
2. $f=2$, the function is $f(x)=e^{ax+b}(a\in[-1,1],b\in[-2,0],a+b\in[-2,0])$
3. $f=3$, the function is $f(x)=ax+b(a\in[-1,1],b\in[0,1],a+b\in[0,1])$

The next $m$ lines each describe an event, which can be one of four types:

1. appear u v: A magic bridge connecting cities $u$ and $v$ appears in the kingdom $(0\le u,v < n, u\ne v)$. It is guaranteed that cities $u$ and $v$ were not reachable from each other before the connection.
2. disappear u v: The magic bridge connecting cities $u$ and $v$ disappears. It is guaranteed that this magic bridge exists.
3. magic c f a b: The magic in the magic ball of city $c$ changes to a function of type $f$ with parameters $a, b$.
4. travel u v x: Query the sum of scores for a person with IQ $x$ traveling from city $u$ to city $v$ (passing through all cities on the path, including $u$ and $v$). If $u$ cannot reach $v$, output the string unreachable.

Output

Output to standard output.

For each query, output one real number per line, representing the sum of scores.

Examples

Input 1

3 7 C1
1 1 0
3 0.5 0.5
3 -0.5 0.7
appear 0 1
travel 0 1 0.3
appear 0 2
travel 1 2 0.5
disappear 0 1
appear 1 2
travel 1 2 0.5

Output 1

9.45520207e-001
1.67942554e+000
1.20000000e+000

Constraints

For 100% of the data, $1\le n\le 100000, 1\le m \le 200000$.

There are 20 test cases in total, each worth 5 points.

Meaning of data types:

• A: No disappear events, and in all appear events, $u=v-1$.
• B: No disappear events.
• C: The total number of cities passed by all travel events is $\le 5000000$ (unreachable city pairs are not counted).

• D: No restrictions.

• 0: In all travel events, $x=1$ (i.e., everyone's IQ is $1$).

• 1: No restrictions.

Scoring

If your answer is within a relative error of $10^{-7}$ or an absolute error of $10^{-7}$ from the standard answer, it is judged as correct.

If all your answers are correct, you get full marks; otherwise, you get 0 points.

Please note the output format: output one answer per line. The answer can only be unreachable or a real number (scientific notation is recommended). The length of each line must not exceed 50 characters. Incorrect output formats will be judged as 0 points.

Note

If the $n$-th derivative of a function $f(x)$ is continuous on the interval $[a, b]$, then applying the Lagrange Mean Value Theorem $n$ times to $f(x)$ at $x_0 (x_0 \in [a, b])$ yields the Taylor expansion with the Lagrange remainder term:

$$f(x)=f(x_0)+\frac{f'(x_0)(x-x_0)}{1!}+\frac{f''(x_0)(x-x_0)^2}{2!}+ \cdots +\frac{f^{(n-1)}(x_0)(x-x_0)^{n-1}}{(n-1)!}+\frac{f^{(n)}(\xi)(x-x_0)^n}{n!},x\in[a,b]$$

Where, when $x > x_0$, $\xi \in [x_0, x]$. When $x < x_0$, $\xi \in [x, x_0]$.

$f^{(n)}$ denotes the $n$-th derivative of the function $f$.