Description

As stated, given a tree with $N$ nodes (connected and acyclic), each node stores a value. Support the following operations:

• 1 x y z: add $z$ to the value of every node on the shortest path from $x$ to $y$ in the tree.
• 2 x y: query the sum of values of all nodes on the shortest path from $x$ to $y$ in the tree.
• 3 x z: add $z$ to the value of every node in the subtree rooted at $x$.
• 4 x: query the sum of values of all nodes in the subtree rooted at $x$.

Input Format

The first line contains $4$ positive integers $N, M, R, P$, representing the number of nodes in the tree, the number of operations, the index of the root, and the modulus, respectively (i.e., all outputs are taken modulo this).

The next line contains $N$ non-negative integers, representing the initial value at each node in order.

The next $N-1$ lines each contain two integers $x, y$, indicating an edge between nodes $x$ and $y$ (guaranteed acyclic and connected).

The next $M$ lines each contain several positive integers; each line represents one operation.

Output Format

Output several lines, each being the result of operation type 2 or 4 (taken modulo $P$), in order.

5 5 2 24
7 3 7 8 0 
1 2
1 5
3 1
4 1
3 4 2
3 2 2
4 5
1 5 1 3
2 1 3

2
21

Hint

[Constraints]

For $30\%$ of the testdata: $1 \leq N \leq 10$, $1 \leq M \leq 10$.

For $70\%$ of the testdata: $1 \leq N \leq {10}^3$, $1 \leq M \leq {10}^3$.

For $100\%$ of the testdata: $1 \le N \le {10}^5$, $1 \le M \le {10}^5$, $1 \le R \le N$, $1 \le P \le 2^{30}$. All input numbers are within the int range.

[Sample Explanation]

The structure of the tree is as follows:

The operations are as follows:

Therefore, the outputs should be $2$ and $21$ in order.

Translated by ChatGPT 5