B'Li Hua has a tree of n vertices and n-1 edges. The root of the tree is vertex 1 . Each vertex i has importance a_i . Denote the size of a subtree as the number of vertices in it, and the importance as the sum of the importance of vertices in it. Denote the heavy son of a non-leaf vertex as the son with the largest subtree size. If multiple of them exist, the heavy son is the one with the minimum index. Li Hua wants to perform m operations: Suppose you were Li Hua, please solve this problem. The first line contains 2 integers n,m ( 2 <= n <= 10^{5},1 <= m <= 10^{5} ) -- the number of vertices in the tree and the number of operations. The second line contains n integers a_{1},a_{2}, ldots ,a_{n} ( -10^{9} <= a_{i} <= 10^{9} ) -- the importance of each vertex. Next n-1 lines contain the edges of the tree. The i -th line contains two integers u_i and v_i ( 1 <= u_i,v_i <= n , u_i ne v_i ) -- the corresponding edge. The given edges form a tree. Next m lines contain operations -- one operation per line. The j -th operation contains two integers t_{j},x_{j} ( t_{j} in {1,2 } , 1 <= q x_{j} <= q n , x_{j} neq 1 if t_j = 2 ) -- the j -th operation. For each query "1 x ", output the answer in an independent line. In the first example: The initial tree is shown in the following picture: The importance of the subtree of 6 is a_6+a_7=2 . After rotating the heavy son of 3 (which is 6 ) up, the tree is shown in the following picture: The importance of the subtree of 6 is a_6+a_3+a_7=3 . The importance of the subtree of 2 is a_2+a_4+a_5=3 . '...