Description

The underachiever Xiao R (pinyin) was tortured by university mathematics courses to the point of being unable to take care of himself. His calculus score was once the lowest among all the courses he took in the classroom. However, one of his roommates surnamed Chen could easily get full marks in math exams. To improve his math grades, one night (in his sleep), he arrived at the Kingdom of Mathematics.

In the Kingdom of Mathematics, everyone’s IQ is represented by a real number in $[0,1]$. There are $n$ cities numbered from $0 \sim n-1$, connected by several magic bridges. At the center of each city there is a magic orb, and inside each magic orb lies a math problem.

After solving this problem, everyone will receive a score in $[0,1]$. A problem can be represented by a function $f(x)$. If a person’s IQ is $x$, then after solving this problem he will receive $f(x)$ points. There are three forms:

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

The magic bridges in the Kingdom of Mathematics change over time. Sometimes a magic bridge disappears, and sometimes a magic bridge appears. However, at any moment, there exists 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.

King Lagrange of the Kingdom of Mathematics is happy to teach Xiao R (pinyin) math, but only if Xiao R first answers the king’s questions. These questions have the same form: for a person with IQ $x$ traveling from city $u$ to city $v$ (i.e., passing through all cities on the path $u \to v$, including $u$ and $v$) and solving all the problems in those cities, what is the sum of all his scores.

Input Format

The first line contains two positive integers $n, m$ and a string $type$. They indicate that there are $n$ cities in the Kingdom of Mathematics, $m$ events occur, and the type of this testdata is $type$.

The string $type$ is provided to help you obtain partial scores more easily; you may not need to use it. Its meaning is explained in Constraints and Assumptions.

The next $n$ lines describe, for each city $i$, the function inside its magic orb in the initial state. One integer $f$ denotes the type of function, and two real numbers $a, b$ denote the parameters. If

• $f=1$, then the function is $f(x)=\sin(ax+b)$.
• $f=2$, then the function is $f(x)=\text e^{ax+b}$.
• $f=3$, then the function is $f(x)=ax+b$.

The next $m$ lines each describe an event, of one of four types.

• appear u v means a magic bridge appears between cities $u$ and $v$. It is guaranteed that before adding the bridge, $u$ and $v$ are not reachable from each other.
• disappear u v means the magic bridge between $u$ and $v$ disappears. It is guaranteed that this magic bridge exists.
• magic c f a b means the magic orb in city $c$ changes to a function of type $f$ with parameters $a, b$.
• travel u v x asks: for a person with IQ $x$ traveling from city $u$ to city $v$, what is the sum of his scores. If $u$ cannot reach $v$, output a single line containing the string unreachable.

Output Format

For each query, output one line with a real number representing the total score.

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

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

Hint

Constraints and Assumptions.
For $100\%$ of the data, $1\le n\le 10^5, 1\le m \le 2 \times 10^5$.

There are 20 testdata points, each worth 5 points.

测试点	$n$	$m$	数据类型
$1$	$\leq 100$	$\leq 200$	C1
$2 \sim 5$	$\leq 10^5$	$\leq 2 \times 10^5$	A0
$6$			B0
$7 \sim 8$			D0
$9 \sim 14$			A1
$15 \sim 17$			C1
$18 \sim 20$			D1

Meaning of data types:

• A: There is no disappear event, and in all appear events, $u = v - 1$.

• B: There is no disappear event.

• C: The total number of cities traversed over all travel events is $\le 5 \times 10^6$ (pairs that are unreachable are not counted).

• D: No further restrictions.

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

• 1: No restriction.

Scoring criteria.

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

You will receive full score only if all your answers are correct; otherwise, you receive 0 points.

Please pay attention to the output format: print one answer per line, and each line must be either unreachable or a real number (scientific notation is recommended). Each line must not exceed 50 characters. Incorrect output format will result in 0 points.

Xiao R Teaches You Math.

If the $n$-th derivative of a function $f(x)$ is continuous on the interval $[a,b]$, then by applying the Lagrange mean value theorem $n$ times to $f(x)$ at $x_0 \ (x_0\in[a,b])$, we obtain the Taylor expansion with Lagrange remainder

$$f(x)=\sum_{k=0}^{n-1}\frac{f^{(k)}(x_0)(x-x_0)^k}{k!}+\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$.

Translated by ChatGPT 5