已知一棵包含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取模）。

【数据范围】
对于 30% 的数据： 1≤N≤10, 1≤M≤10;
对于 70% 的数据1≤N≤10^3， 1≤M≤10^3
对于 100% 的数据： 1≤N≤10^5, 1≤M≤10^5，1≤R≤N，1≤P≤2^30。所有输入的数均在int范围内。
【样例解释】
树的结构为：
各操作如下表所示：