友情提示：380元/半年，儿童学编程，就上码丁实验室。
【题目描述】
社会送温暖有非常多的体现方式，小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}$。