3029: 社会主义送温暖

小G十分喜欢社会主义，这天他开始研究社会主义的优越性。

社会主义乐于送温暖，这有非常多的体现方式，小G正在思考其中的一种：

我们可以把社会看做一个n个节点的树，由n−1条边连接，节点从1编号。每个节点有一定财富值，用金币数描述。

每次社会主义送温暖时，他会选择两个节点，对链接它们的道路上的点， 采用这么几种方式：

1 按顺序加金币数，第一个加a，第二个加a + d，第三个加a + 2d，以此类推。

2 按顺序加金币数。第一个个a，第二个加2a，第三个加4a，以此类推。

3 按顺序改金币数，第一个改为a，第二个改为a+d，第三个改为a+2d， 以此类推。

4 按顺序改金币数，第一个改为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