题目描述

社会送温暖有非常多的体现方式，小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}$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共8个测试点，非原站或官方原始数据。总分100分。