Math Kingdom Challenge

In the Math Kingdom, every citizen has an intelligence quotient (IQ) represented by a real number in the interval \([0,1]\). There are \(n\) cities numbered from \(0\) to \(n-1\). Each city hosts a magical ball at its center that contains a math problem. A person with IQ \(x\) who solves the problem in a city obtains a score \(f(x)\) which is guaranteed to lie in \([0,1]\). The problem in each city is given by one of the following three functions:

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

The kingdom’s magical bridges connect cities but change over time. At any moment there is at most one simple path between any two cities (i.e. the cities form a forest). Initially, there are no bridges. There are three types of operations:

1. Add Bridge: "1 u v" adds a magical bridge connecting city \(u\) and city \(v\).
2. Remove Bridge: "2 u v" removes the magical bridge between city \(u\) and city \(v\).
3. Query: "3 u v x" asks: if a person with IQ \(x\) travels from city \(u\) to city \(v\) (along the unique path through the current forest, including both endpoints) and solves the math problem in each city on that path, what is the total score?

Your task is to process \(m\) operations. For each query operation, output the sum of scores with at least 6 decimal places.

inputFormat

The first line contains two integers (n) and (m), denoting the number of cities and the number of operations respectively. Then (n) lines follow, each describing a city. Each line contains a string and two real numbers: the string indicates the type of function for the city (it can be "sin", "exp", or "linear"), and the two numbers are the parameters (a) and (b) for the function. Then (m) lines follow, each describing an operation in one of the following formats:

1 u v 2 u v 3 u v x

Here, operation "1 u v" adds a magic bridge between cities (u) and (v); operation "2 u v" removes the bridge between (u) and (v); and operation "3 u v x" queries the total score (with a person having IQ (x)) when traveling from (u) to (v) along the unique path.

outputFormat

For each query operation (type 3), output a line containing the total score obtained, formatted to at least 6 decimal places.

sample

3 6
sin 0.5 0.3
exp -0.5 -1.0
linear 0.2 0.5
1 0 1
1 1 2
3 0 2 0.5
2 1 2
3 0 1 0.0
1 1 2
3 0 2 1.0

1.409192
0.663399
1.640486