Informática Avançado - Semana 56

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