#P18572. Mafia and Candies

Mafia and Candies

Mafia and Candies

某个王国有 nn 座城市,编号为 1,2,…,n1,2,\ldots,n,其中城市 11 是首都。王国恰有 n−1n-1 条双向道路,所有城市都能通过这些道路到达首都。因此,道路构成一棵树。

王国的每座城市中都有黑手党团伙。城市 ii 中最初恰有 aia_i 名黑手党成员。你是一位糖果商人,会不时把糖果从一座城市运往另一座城市,但经营过程中会发生以下事情。

  1. 每当装有糖果的车到达城市 ii,当地团伙就会抢走糖果,尽可能地在全部成员之间均分。不能均分的剩余糖果留给车夫。也就是说,若车到达时有 xx 颗糖果,离开该城市时就剩下 x mod aix\bmod a_i 颗糖果。
  2. 相邻城市的团伙可能发生冲突,导致连接它们的道路被毁。与首都断开的连通块中会出现混乱:其中每座城市的团伙都会增加一些成员。随后,国王会修建一条新路,从仍与首都连通的一座指定城市,连接到被毁道路中与首都断开的那个端点,恢复整个王国的连通性。
  3. 团伙的宣传或国王的清剿可能改变一座城市的团伙人数;此时人数会被直接设为指定值。

你已经提前得知所有这些事件。对每次从城市 uu 运送 xx 颗糖果到城市 vv 的运输,你想知道最终能送到顾客手中的糖果数。

输入格式

第一行包含两个整数 n,qn,q(2≤n≤1052\le n\le 10^5,1≤q≤1051\le q\le 10^5),分别表示城市数和事件数。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n(1≤ai≤10121\le a_i\le 10^{12}),表示各座城市最初的黑手党人数。

接下来 n−1n-1 行描述道路,每行包含两个整数 x,yx,y(1≤x,y≤n1\le x,y\le n),表示城市 x,yx,y 之间有一条道路。保证这些道路构成一棵有 nn 个顶点的树。

接下来 qq 行按时间顺序描述事件。每行的第一个整数为 t∈{1,2,3}t\in\{1,2,3\}。

  • 若 t=1t=1,该行格式为 1 u v x,其中 1≤u,v≤n1\le u,v\le n,1≤x≤10121\le x\le 10^{12}。把一车 xx 颗糖果从 uu 运往 vv。车辆按照从 uu 到 vv 的方向经过当前树上的简单路径,路径上的每座城市都会抢夺一次,包括起点 uu 和终点 vv。运输不改变团伙人数;即使糖果数变成 00,这次运输的最终结果也是 00。
  • 若 t=2t=2,该行格式为 2 x y z d,其中 1≤x,y,z≤n1\le x,y,z\le n,0≤d≤1070\le d\le 10^7。先毁掉城市 x,yx,y 之间的道路,使王国分成两个连通块。在不包含首都的连通块中,每座城市的团伙人数都增加 dd。随后,从城市 zz 向 x,yx,y 中位于这个断开连通块内的那个端点修建新道路。
  • 若 t=3t=3,该行格式为 3 i y,其中 1≤i≤n1\le i\le n,1≤y≤10121\le y\le 10^{12}。把城市 ii 的团伙人数设为 yy。

对每个第二类事件,保证当时城市 x,yx,y 之间确有道路,并且该道路被毁后,城市 zz 仍能到达首都。

注意,第二类事件中的增加可能让实际团伙人数超过初始人数的上界 101210^{12}。输入只有这一组树和事件,不含测试组数。

输出格式

对每个第一类事件,输出一行一个整数,表示从 uu 运到 vv 后剩余的糖果数。

对每个第二类事件,输出一行一个整数,表示人数增加之后、新道路修建之前,与首都断开的那个连通块内的团伙人数总和。

第三类事件不输出任何内容。

样例

输入

4 11
5 6 2 5
1 2
4 2
2 3
1 4 4 7
1 3 4 5
1 4 3 5
3 4 4
1 2 4 11
1 2 4 9
2 4 2 3 3
1 2 4 9
2 3 4 1 0
1 2 4 9
1 2 4 11

输出

2
1
0
1
3
7
1
7
3
0