Cây lan truyền

Cho một cây có $n$ đỉnh đánh số từ $1$ đến $n$, gốc là đỉnh $1$. Mỗi đỉnh $i$ có một giá trị ban đầu $a_i$.

Cây có một tính chất đặc biệt: khi cộng giá trị $val$ vào đỉnh $i$, thì giá trị $-val$ sẽ được cộng vào tất cả các con trực tiếp của $i$. Tiếp theo, giá trị $-(-val)=val$ lại được cộng vào các con của các con đó, và cứ tiếp tục lan truyền như vậy đến hết cây con của $i$. Nói cách khác, nếu đỉnh $u$ nằm trong cây con gốc $i$ và độ sâu của $u$ trong cây ban đầu chênh với $i$ là $k$ cạnh, thì $u$ nhận thêm $(-1{)}^k·val$.

Bạn cần xử lý $m$ truy vấn thuộc một trong hai dạng:

• 1 x val — cộng $val$ vào giá trị của đỉnh $x$ (kèm hiệu ứng lan truyền nêu trên).
• 2 x — in ra giá trị hiện tại của đỉnh $x$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$ — giá trị ban đầu của các đỉnh.
• $n-1$ dòng tiếp theo, mỗi dòng chứa hai số $v_i$ và $u_i$ mô tả một cạnh của cây.
• $m$ dòng cuối, mỗi dòng chứa một truy vấn theo định dạng đã mô tả.

Dữ liệu ra

Với mỗi truy vấn loại 2, in giá trị tương ứng trên một dòng riêng, theo đúng thứ tự xuất hiện trong dữ liệu vào.

Ràng buộc

• $1\le n,m\le 2·{10}^5$
• $1\le a_i\le 1000$
• $1\le v_i,u_i\le n$
• $1\le x\le n$, $1\le val\le 1000$ cho mọi truy vấn.

Ví dụ