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

Entrada	Saída
5 5 1 2 1 1 2 1 2 1 3* 2 4 2 5 1 2 3 1 1 2 2 1 2 2 2 4	3 3 0