409014 - 重链剖分

已知一棵包含 N 个结点的树(连通且无环),每个结点上包含一个数值,需要支持以下操作: 1 x y z,表示将树从 x 到 y 结点最短路径上所有结点的值都加上 z。 2 x y,表示求树从 x 到 y 结点最短路径上所有结点的值之和。 3 x z,表示将以 x 为根结点的子树内所有结点值都加上 z。 4 x 表示求以 x 为根结点的子树内所有结点值之和。

输入

第一行包含 4 个正整数 N, M, R, P,分别表示树的结点个数、操作个数、根结点序号和取模数(即所有的输出结果均对此取模)。 接下来一行包含 N 个非负整数,分别依次表示各个结点上初始的数值。 接下来 N − 1 行每行包含两个整数 x, y,表示点 x 和点 y 之间连有一条边(保证无环且连通)。 接下来 M 行每行包含若干个正整数,每行表示一个操作。

输出

输出包含若干行,分别依次表示每个操作 2 或操作 4 所得的结果(对 P 取模)。

样例

输入

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

提示

对于 100% 的数据: 1 ≤ N ≤ 10^5,1 ≤ M ≤ 10^5,1 ≤ R ≤ N,1 ≤ P ≤ 2^30。所有输入的数均在 int 范围内。

时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题