给一棵含有 n 个结点的有根树，根结点为 1 ，编号为 i 的点有点权 a_i（i ∈ [1, n]）。现在有两种操作，格式如下： 

• 1 x y 该操作表示将点 x 的点权改为 y 。 

• 2 x 该操作表示查询以结点 x 为根的子树内的所有点的点权和。 

现有长度为 m 的操作序列，请对于每个第二类操作给出正确的结果。 

输入的第一行包含两个正整数 n, m ，用一个空格分隔。 

第二行包含 n 个整数 a₁, a₂, ..., a_n ，相邻整数之间使用一个空格分隔。

接下来 n − 1 行，每行包含两个正整数 u_i , v_i ，表示结点 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。