树上路径与子树操作

题目描述

Y 同学有一棵包含 $N$ 个节点的连通无向树，树的根节点编号为 $R$。每个节点 $i$（$1 \le i \le N$）上都有一个初始的非负整数权值 $A_i$。

Y 同学需要在这棵树上依次进行 $M$ 次操作，并给定了一个全局的模数 $P$。操作共分为以下四种类型：

1. 1 x y z：将树上从节点 $x$ 到节点 $y$ 的简单路径上的所有节点的权值增加 $z$。
2. 2 x y：查询树上从节点 $x$ 到节点 $y$ 的简单路径上的所有节点的权值之和，并求出其对 $P$ 取模后的结果。
3. 3 x z：将以节点 $x$ 为根的子树内所有节点的权值增加 $z$。
4. 4 x：查询以节点 $x$ 为根的子树内所有节点的权值之和，并求出其对 $P$ 取模后的结果。

请你编写程序帮助 Y 同学高效地执行这些修改与查询操作。

输入格式

第一行包含四个正整数 $N, M, R, P$，相邻两个整数之间由一个空格隔开，分别表示树的节点个数、操作的总次数、树的根节点编号以及取模所用的模数。

第二行包含 $N$ 个非负整数 $A_1, A_2, \dots, A_N$，相邻两个整数之间由一个空格隔开，依次表示各个节点的初始权值。

接下来的 $N-1$ 行，每行包含两个整数 $U$ 和 $V$，表示节点 $U$ 和节点 $V$ 之间连有一条无向边。保证输入的边构成了一棵无环且连通的树。

接下来的 $M$ 行，每行首先包含一个整数 $op$ 表示操作的类型（$op \in \{1, 2, 3, 4\}$），随后包含若干个正整数，表示该操作的参数，具体格式和含义如题目描述所述。

输出格式

对于每一次操作类型为 2 或 4 的查询操作，输出一行一个整数，表示该次查询的权值总和对 $P$ 取模后的结果。

样例

样例输入 #1

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

样例输出 #1

2
21

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le N \le 10^5$，$1 \le M \le 10^5$，$1 \le R \le N$，$1 \le P \le 2^{30}$。输入的所有的初始权值和每次增加的值均在 32 位有符号整数的表示范围内。

在计算路径或子树的权值总和时，累加的结果可能超过 32 位有符号整数的范围，请使用 64 位整数类型进行运算和存储。