Description

You have a rooted tree with root $1$, with nodes numbered $1\sim n$. Node $i$ has an integer weight $a_i$. At the same time, every node is colored red or blue. Initially, all nodes are red. You need to maintain this tree and process $q$ operations. There are several types of operations, with the following formats:

• 1 x v: Increase the weight of every node in the subtree of node $x$ by $v$, and take modulo $p$.
• 2 x v: Set $a_x$ to $v$. Note that this does not assign the entire subtree.
• 3 x: Color node $x$ blue. Let node $j$ be the predecessor of node $x$ in the ranking by node index (not by weight) among its red sibling nodes. Delete the edge connecting node $x$ to its parent. Then attach node $x$ as a child of node $j$. If node $x$ has no red siblings, or all its red siblings have indices greater than $x$, then do nothing.
• 4 x: Let $S$ be the set of weights in the subtree of $x$ whose occurrence counts are odd. Output the sum of the $k$-th power of each number in the set, modulo $998244353$. That is, $(\sum_{z\in S}z^k)\bmod 998244353$.

In particular, the testdata guarantees that each node can be operated by operation 3 at most once. In other words, there will be no case where operation 3 is applied to a blue node.

Input Format

The first line contains four integers $n,q,p,k$.
The second line contains $n$ integers, representing the initial $a_1,a_2,\cdots,a_n$.
The next $n-1$ lines each contain two integers $f,t$, representing an undirected tree edge $f \leftrightarrow t$.
The next $q$ lines each contain two or three integers $op,x(,v)$.

Output Format

For each query operation, output one integer per line as the answer.

10 10 500 1
3 2 1 2 1 3 2 1 3 4
1 4
7 8
3 6
8 10
2 3
2 5
8 9
7 2
2 1
4 1
1 3 1
2 1 2
4 1
4 3
4 6
1 4 1
3 7
1 5 1
4 5

10
5
6
4
12

Hint

Sample Explanation

Sample #1

• Query 4 1: The weights in the subtree are $3,2,1,2,1,3,2,1,3,4$. The set $S$ is $\{1,2,3,4\}$, so the answer is $10$.
• Update 1 3 1: The weights of all nodes become $3,2,2,2,1,4,2,1,3,4$.
• Update 2 1 2: The weights of all nodes become $2,2,2,2,1,4,2,1,3,4$.
• Query 4 1: The weights in the subtree are $2,2,2,2,1,4,2,1,3,4$. The set $S$ is $\{2,3\}$, so the answer is $5$.
• Query 4 3: The nodes in the subtree are $3,6$, with weights $2,4$. The set $S$ is $\{2,4\}$, so the answer is $6$.
• Query 4 6: Since this is a leaf node, the subtree contains only itself with weight $4$. The set $S$ is $\{4\}$, so the answer is $4$.
• Update 1 4 1: The weights of all nodes become $2,2,2,3,1,4,2,1,3,4$.
• Update 3 7: Color $7$ blue, delete the edge $2\leftrightarrow 7$, and attach $7$ as a child of $5$.
• Update 1 5 1: The weights of all nodes become $2,2,2,3,2,4,3,2,4,5$.
• Query 4 5: The nodes in the subtree are $5,7,8,9,10$, with weights $2,3,2,4,5$. The set $S$ is $\{3,4,5\}$, so the answer is $12$.

Constraints

This problem uses bundled testdata.

For all testdata, $1\le x\le n\le 10^5$, $1\le q \le 10^5$, $0 \le a_i, v < p \le 500$, $p\ne 0$, $0\le k \le 10^9$.

Translated by ChatGPT 5