C. Tree Score
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Chopper and Usopp find a giant plant shaped like a tree with $$$n$$$ vertices and $$$n-1$$$ branches. Vertex $$$v$$$ has a value $$$a_{v}$$$.

For each branch $$$i$$$, two values are written:

  • $$$p_{i}$$$, its contribution if the branch is kept;
  • $$$q_{i}$$$, its contribution if the branch is cut.

Consider any subset $$$K$$$ of branches. Branches in $$$K$$$ are kept, and all other branches are cut. The kept branches split the vertices into several connected components.

For a component $$$C$$$, define its value as: $$$$$$W(C) = \sum_{v \in C} a_{v}$$$$$$

The score of choice $$$K$$$ is: $$$$$$score(K) = \left(\prod_{i \in K} p_{i}\right) \left(\prod_{i \notin K} q_{i}\right) \left(\prod_{C} W(C)\right)$$$$$$ where the last product is over all connected components after cutting the branches not in $$$K$$$.

Define: $$$$$$F = \sum score(K)$$$$$$ In other words, $$$F$$$ is the sum of $$$score(K)$$$ over all $$$2^{n-1}$$$ possible choices of which branches are kept and which are cut.

All calculations are performed modulo 998244353.

You must process $$$Q$$$ updates. After each update, output the current value of $$$F$$$.

There are two types of updates:

  • $$$1\ v\ x$$$: set $$$a_{v}=x$$$.
  • $$$2\ i\ p\ q$$$: set $$$p_{i}=p$$$ and $$$q_{i}=q$$$.
Branches are numbered from 1 to $$$n-1$$$ in their input order.
Input

The first line contains two integers $$$n$$$ and $$$Q$$$ ($$$1 \le n, Q \le 2 \times 10^{5}$$$) — the number of vertices and the number of updates.

The second line contains $$$n$$$ integers $$$a_{1}, a_{2}, \dots, a_{n}$$$ ($$$0 \le a_{v} \lt 998244353$$$) — the vertex values.

The $$$i$$$-th of the next $$$n-1$$$ lines contains four integers $$$u_{i}$$$, $$$v_{i}$$$, $$$p_{i}$$$, and $$$q_{i}$$$ ($$$1 \le u_{i}, v_{i} \le n$$$, $$$0 \le p_{i}, q_{i} \lt 998244353$$$) — the ends and the two values of the $$$i$$$-th branch.

It is guaranteed that these branches form a tree.

Each of the next $$$Q$$$ lines contains one update in one of the following formats:

  • $$$1\ v\ x$$$ ($$$1 \le v \le n$$$, $$$0 \le x \lt 998244353$$$).
  • $$$2\ i\ p\ q$$$ ($$$1 \le i \le n-1$$$, $$$0 \le p, q \lt 998244353$$$).
Output

After each update, output one integer — the current value of $$$F$$$ modulo 998244353.

Example
Input
2 2
1 2
1 2 3 5
1 1 4
2 1 1 2
Output
58
22
Note

After the first update, the vertex values are 4 and 2.

If the edge is kept, the contribution is $$$3 \times (4+2) = 18$$$. If the edge is removed, the contribution is $$$5 \times 4 \times 2 = 40$$$. Therefore, $$$F = 18 + 40 = 58$$$.

After the second update, the edge values become $$$p_{1}=1$$$ and $$$q_{1}=2$$$, so $$$F = 1 \times (4+2) + 2 \times 4 \times 2 = 22$$$.