給一棵含有 n 個結(jié)點的有根樹，根結(jié)點為 1 ，編號為 i 的點有點權(quán) a_i（i ∈ [1, n]）。現(xiàn)在有兩種操作，格式如下： 

? 1 x y 該操作表示將點 x 的點權(quán)改為 y 。 

? 2 x 該操作表示查詢以結(jié)點 x 為根的子樹內(nèi)的所有點的點權(quán)和。 

現(xiàn)有長度為 m 的操作序列，請對于每個第二類操作給出正確的結(jié)果。 

輸入的第一行包含兩個正整數(shù) n, m ，用一個空格分隔。 

第二行包含 n 個整數(shù) a₁, a₂, ..., a_n ，相鄰整數(shù)之間使用一個空格分隔。

接下來 n ? 1 行，每行包含兩個正整數(shù) u_i , v_i ，表示結(jié)點 u_i 和 v_i 之間有一條邊。

接下來 m 行，每行包含一個操作。 

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

4
5
6
6

對于 30% 的評測用例，n, m ≤ 1000；

對于所有評測用例，1 ≤ n, m ≤ 100000 ，0 ≤ a_i , y ≤ 100000 ，1 ≤ u_i , v_i , x ≤ n。