有一棵點數為 $N$ 的樹，以點 $1$ 為根，且樹有點權。然后有 $M$ 個操作，分為三種：
1、把某個節(jié)點 $x$ 的點權增加 $a$ 。
2、把某個節(jié)點 $x$ 為根的子樹中所有點的點權都增加 $a$ 。
3、詢問某個節(jié)點 $x$ 到根的路徑中所有點的點權和。

第一行包含兩個整數 $N, M$。表示點數和操作數。
接下來一行 $N$ 個整數，表示樹中節(jié)點的初始權值。
接下來 $N-1$ 行每行兩個正整數 $fr,to$， 表示該樹中存在一條邊 ($fr,to$) 。
再接下來 $M$ 行，每行分別表示一次操作。其中第一個數表示該操作的種類（$1-3$） ，之后接這個操作的參數（$x$ 或者 $x\;a$）。

對于每個詢問操作，輸出該詢問的答案。答案之間用換行隔開。

1 2 3 4 5
1 2
1 4
2 3
2 5
3 3
1 2 1
3 5
2 1 2
3 3

6
9
13

數據范圍與提示：
對于 100% 的數據，$N,M≤10^5$ ，且所有輸入數據的絕對值都不會超過 $10^6$ 。