Description

You are given $N$ scales with two sides of negligible mass. The scales are indexed with integers from $1$ to $N$. On each side of the scale, there is either another scale or a single weight (of nonnegligible mass). The scale with index $1$ is set on the ground, while every other scale rests on some other scale. Notice that this implies that there are exactly $N+1$ weights. The weights are indexed with integers from $1$ to $N+1$, and each has an integer mass: $w_{1}, w_{2} \cdots, w_{N+1}$.

The following figure depicts a setup of three scales and four weights as given in the sample test case shown at the end of this problem statement. The numbers in the upright font represent the indices of the scales and the weights, while the numbers in italics represent the masses of the weights. For example, the scale with index $2$ rests on the left side of the scale with index $1$, and the weight with index $2$ and mass $6$ rests on the right side of scale $1$.

We say that a scale is balanced if the total mass of the left side is the same as the total mass of the right side. We say that a scale is super-balanced if it is balanced and if on both sides there is either a super-balanced scale or a weight.

For example, in the figure above, only scale $3$ is balanced (and also super-balanced), but if we increased the mass of weights $3$ and $4$ both to $1.5$, all three scales would become super-balanced. However, if we instead increased the mass of weight $1$ to $4$, scale $1$ would become balanced but not super-balanced, since scale $2$ still wouldn't be balanced.

We are now to process $Q$ operations of two types:

• $1\,k\,w$ : Change the mass of weight $k$ to an integer mass of $w$.
• $2\,s$ : Say we want a scale $s$ to be super-balanced. We can take some of the weights and make them heavier using magic! Note that these new values for the mass do not have to be integers. What is the minimal total mass on scale $s$ necessary to make $s$ super-balanced? Since this number may be quite large, output it modulo $998244353$. It can be shown that given the constraints, the result is always an integer.

Note that the operations of type $1$ change the tree whereas the operations of type $2$ do not.

Input format

In the first line of input, there are two integers: $N$ and $Q$.

The $i$-th (for $i \in\{1, \ldots, N\}$ ) of the following $N$ lines contains two pairs of a character and a number, each pair describing one side of the $i$-th scale: the character is either S (scale) or W (weight), denoting the type of the object on the given side of the scale, and the integer is the index of the appropriate item. It is guaranteed that a scale never rests on a scale with a greater index.

The following line contains $N+1$ integers, $w_{1}, w_{2}, \cdots, w_{N+1}$, representing the masses of the weights.

The final $Q$ lines represent the operations. Each of them is either of the form $1\,k\,w$ or of the form $2\,s$, as described in the problem statement.

Output format

For each operation of the second type, output the appropriate minimum mass modulo $998244353$ in a separate line.

Input bounds

• $1 \leq N \leq 2 \cdot 10^{5}$.
• $1 \leq Q \leq 2 \cdot 10^{5}$.
• $1 \leq w_{i} \leq 10^{9}$.
• For each operation of type $1: 1 \leq k \leq N+1$.
• For each operation of type $1: 1 \leq w \leq 10^{9}$.
• For each operation of type $2: 1 \leq s \leq N$.

Subtasks

For subtasks 2--4, let the depth of a weight be defined as the number of scales on which it rests (directly or indirectly).

1. (9 points) There is a weight on at least one side of every scale.
2. (8 points) Every weight has the same depth.
3. (24 points) Every weight has depth less than $30$. In addition, we have $N, Q \leq 5000$.
4. (14 points) Every weight has depth less than $30$.
5. (14 points) $N, Q \leq 5000$.
6. (31 points) No additional constraints.

3 5
S 2 W 2
W 1 S 3
W 4 W 3
3 6 1 1
2 2
2 1
1 3 2
2 1
2 3

6
12
16
4

To make scale $2$ super-balanced, we increase the mass of weights $3$ and $4$ to $1.5$ each. As a result, scales $2$ and $3$ will both be balanced, and hence $2$ will be super-balanced. The total mass on scale $2$ is $3+1.5+1.5=6$. When we do this, scale $1$ will also be balanced, so it will be super-balanced as well, with a total mass of $6+3+1.5+1.5=12$. When we change the mass of weight $3$ to $2$, this no longer works. Therefore, to make scale $1$ super-balanced, we can make weight $1$ have mass $4$, weight $2$ have mass $8$ and weight $4$ have mass $2$. The total mass would then be $8+4+2+2=16$.