Dynamic Tree Maintenance with Subtree Updates and Queries

You are given a rooted tree with n nodes numbered from 1 to n, with node 1 as the root. Each node i has an integer weight a_i and is initially colored red. You need to maintain the tree under q operations. The operations are as follows:

• 1 x v: For every node in the subtree of node x, increase its weight by v and take the result modulo p. In other words, for every node i in the subtree of x, update
  \(a_i = (a_i + v) \bmod p\).
• 2 x v: Set a_x to v (modulo p). Note that only node x is updated, not its entire subtree.
• 3 x: Change the color of node x to blue. Then, let j be the red sibling of x (i.e. a node having the same parent as x) whose index is the immediate predecessor of x among the red siblings (i.e. the maximum node number less than x, if any). If such a node exists, detach node x from its current parent and attach it as a child of node j. If no red sibling exists or all red siblings have indices greater than x, do nothing.
• 4 x: Let \(S\) be the set of numbers that appear an odd number of times among the weights of the nodes in the subtree of node x. Compute and output
  \(\sum_{z \in S} z^k \bmod 998244353\). Here, the exponent k is given in the input.

It is guaranteed that each node will have the type-3 operation executed at most once.

Input Format: The first line contains four integers n, q, p, and k. The second line contains n integers representing the initial weights \(a_1, a_2, \dots, a_n\) (each given modulo p). The next n-1 lines describe the tree structure. For nodes 2 to n, the i-th line contains a single integer indicating the parent of node i. The following q lines each contain an operation in one of the four formats described above.

Output Format: For every operation of type 4, output the required answer on a new line.

inputFormat

The input is given as follows:

 n q p k
 a1 a2 ... an
 par2
 par3
 ...
 par_n
 op1
 op2
 ...
 op_q

Where:

• n is the number of nodes.
• q is the number of operations.
• p is the modulus used for weight updates.
• k is the exponent used in type-4 queries.
• a_i is the initial weight of node i.
• For nodes 2 to n, each line gives the parent of that node.
• Each of the following q lines represents an operation as described.

outputFormat

For each type-4 operation, output the computed sum on a separate line.

sample

5 7 10 2
1 2 3 4 5
1
1
2
2

4 1
1 2 3
4 2
3 3
4 1
2 4 0
4 2

55
138
148
98