Natal do Flúcio

Flúcio gosta muito de árvores. Como o Natal está chegando ele decide procurar por diferentes tipos de árvores iluminadas para decorar sua casa. Durante a busca, ele descobre as árvores de propagação. Essas árvores possuem uma propriedade especial, elas conseguem mudar a frequência dos pisca-pisca (famosas lâmpadas natalinas) que ficam em seus nós e propagar essa alteração para outros pisca-pisca da árvore.

Depois de muito tempo observando as árvores de propagação Flúcio concluiu que quando uma das lâmpadas recebe uma corrente diferente de energia a mesma sofre uma alteração $$x$$ em sua frequência de piscadas ela altera propaga $$-x$$ piscadas para as lâmpadas que estão diretamente ligadas a ela, e estas propagam $$-(-x) = x$$ para as lâmpadas que estão diretamente ligadas a ela (suas “filhas”), e assim sucessivamente até chegar em uma lâmpada que não possui outras ligações.

Sabendo disso, Flúcio compra uma árvore de propagação e resolve testá-la em casa. Para isso anota a sequência desses testes em seu caderno, que consistem em:

• $$1$$ $$u$$ $$x$$ $$-$$ provoca uma alteração x na frequência de piscadas da lâmpada do nó u.
• $$2$$ $$u$$ $$-$$ consulta a frequência de piscadas da lâmpada do nó u.

Vale lembrar que Flúcio faz $$m$$ anotações em seu caderno e que a árvore possui $$n$$ lâmpadas ($$n$$ nós) e que a lâmpada $$1$$ é a raíz da ávore.

Entrada

A entrada é composta por dois inteiros $$n$$ e $$m$$ $$(1 \leq n, m \leq 200000)$$. A segunda linha contém n inteiros $$a_1, a_2, …, a_n$$ $$(1 \leq a_i \leq 1000)$$. Cada uma das próximas $$n – 1$$ contém dois inteiros $$u_i$$ e $$v_i$$ $$(1 \leq u_i, v_i \leq n)$$ representando uma ligação entre as lâmpadas $$u_i$$ e $$v_i$$. Cada uma das próximas $$m$$ contém um teste feito por Flúcio no formato descrito anteriormente. E garantido para todas as anotações que: $$1 \leq u \leq n$$ e $$1 \leq x \leq 1000$$.

Saída

Para cada um dos testes tipo $$2$$ você deve imprimir a resposta. Os testes devem ser respondidos na ordem que foram apresentados na entrada.

Exemplos