Weights

You are given N scales, each having two pans with negligible mass. The scales are numbered from 1 to N and arranged in a tree: scale 1 is placed on the ground, and every other scale is placed on one of the pans of another scale. There are N+1 weights, numbered from 1 to N+1, with initial masses given by integers \(w_1, w_2, \dots, w_{N+1}\).

Each scale has two pans. For each scale, if a pan does not hold a child scale then a weight is placed on it. The assignment of weights is uniquely determined as follows. After the positions of all scales are given, traverse scales from 1 to N in order. For each scale, check the left pan then the right pan; if a pan has no scale attached then assign the next available weight (in increasing order of weight id) to that pan.

A scale is balanced if the total mass on its left pan equals that on its right pan. Furthermore, a balanced scale is said to be super-balanced if its two pans both contain either weights or (super-balanced) scales.

You are asked to process Q operations of the following two types:

• 1 k w: Change the mass of weight k to integer w.
• 2 s: Suppose we want to make scale s super-balanced. By magic you are allowed to increase the masses of some weights (the new masses may be non‐integers) but you are not allowed to decrease any weight. What is the minimum total mass on scale s that can be achieved so that it is super-balanced? Since the answer might be huge, output it modulo 998244353. It can be proved that under the given restrictions the answer is always an integer.

Note that operations of type 1 change the weights permanently, while type 2 operations are queries.

Input Format

The first line contains two integers N and Q.

The second line contains N+1 integers \(w_1, w_2, \dots, w_{N+1}\) representing the initial masses of the weights.

Then follow N-1 lines. For each scale i from 2 to N, a line contains an integer p and a character c (either L or R), indicating that scale i is placed on the c pan of scale p.

After that, there are Q lines, each describing an operation. An operation is either in the form 1 k w or 2 s as explained above.

Output Format

For each query of type 2, output a single line containing the answer modulo 998244353.

---

Explanation of the Magic:
To make a scale super-balanced, suppose its two pans (after recursively ensuring the substructures are super-balanced) have minimum achievable masses L and R respectively. By magic, you are allowed to increase the mass on a pan (if needed) up to any value as long as it is at least the original value. Hence, the minimum achievable mass for that scale is
\[ 2\cdot \max(L, R)\] since both pans must be raised to \(\max(L, R)\).

Note: We treat weights as leaves. For a weight with current mass w, the minimum achievable mass is simply w (since you are not allowed to decrease it, though you may increase it to match the other side if needed).

inputFormat

The first line contains two integers N and Q.

The second line contains N+1 integers \(w_1, w_2, \dots, w_{N+1}\) representing the initial masses of the weights.

Then follow N-1 lines. For each scale i from 2 to N, a line contains an integer p and a character c (L or R), meaning scale i is placed on the c pan of scale p.

After that, there are Q lines, each representing an operation in one of the following forms:

• 1 k w : update the mass of weight k to integer w.
• 2 s : query the minimum total mass for scale s to be super-balanced (using magic to increase weights, if necessary).

Weight Assignment: For each scale from 1 to N (in order), if its left pan is not occupied by a scale (via the input above), assign the next weight to that pan. Then do the same for the right pan. Thus, all unoccupied pans are filled with weights, and weights are numbered from 1 to N+1 accordingly.

outputFormat

For each operation of type 2, output a single line containing the minimum total mass on the queried scale (after using magic as necessary) modulo 998244353.

sample

3 3
3 6 2 4
1 L
2 R
2 3
1 4 5
2 1

8
40

</p>