社会送温暖

【题目描述】

社会送温暖有非常多的体现方式，小G正在思考其中的一种： 我们可以把社会看做一个$n$个节点的树，由$n-1$条边连接，节点从$1$编号，每个节点有一定财富值，用金币数描述。 每次社会送温暖时，他会选择两个节点，对链接它们的道路上的点，采用这么几种方式： ①.按顺序加金币数，第一个加$a$，第二个加$a+d$，第三个加$a+2d$，以此类推。 ②.按顺序加金币数，第一个加$a$，第二个加$2a$，第三个加$4a$，以此类推。 ③.按顺序改金币数，第一个改为$a$，第二个改为$a+d$，第三个改为$a+2d$，以此类推。 ④.按顺序改金币数，第一个改为$a$，第二个改为$2a$，第三个改为$4a$，以此类推。 有时社会送温暖还要考虑两个点路径间的民众反映，所以会询问路径上的金币数和，你要告诉他答案模$P$的值。

【输入】

第一行三个数$n,q,P$，分别表示节点数、操作数、和模数。 接下来$n-1$行每行两个整数表示一条边。 接下来$1$行$n$个整数，第$i$个整数$A_i$表示这个点上初始的金币数。 接下来$q$行每行三个数$op,u,v$，表示操作类型与操作的两个点。 若$op=1$或$op=3$，则这行后还会接两个整数$a$和$d$，如题面所描述；若$op=2$或$op=4$，则这行后还会接一个整数$a$；若$op=5$，则表示询问。

【输出】

对每个询问操作输出一行作为答案。

【输入样例】

5 5 29311
1 3
5 3
4 3
3 2
24701 12247 27130 27071 4060
4 5 1 27096
4 2 3 17348
3 1 2 8785 8918
5 3 5
4 2 1 2936

【输出样例】

15488

【提示】

【数据规模】 20%的数据：$n,q≤1000$。 40%的数据：$n,q≤10000$。 另有30%的数据：树是一条链。 100%的数据：$1≤n,q≤10^5;1≤P≤10^7;0≤A_i,d,a≤2^{31}$。