SPOJ Brasil

Com a proximidade da copa do mundo, as empresas de televisão estão trabalhando a todo vapor para transmitir o campeonato com a maior qualidade possível. Poucos sabem, mas a computação e matemática estão fortemente relacionada as tecnologias responsáveis pela transmissão dos jogos.

Uma exemplificação disso é o uso do XOR (Ou exclusivo), ele é bastante importante no processamento de imagens. Seu uso é importante por exemplo na detecção de mudanças em imagens.

Uma das maquinas responsáveis por tratar imagens é bem antiga, e seu algoritmo é histórico e lento. Essa maquina é uma arvore com N nós cada um possuindo um valor que recebe diversos pedidos de mudança em um certo intervalo desses valores. Explicitamente ela funciona da seguinte forma:

• A maquina nada mais é que uma arvore com N nós enraizada no nó de valor 1
• Cada nó possui um valor V_i diferente ou não dos demais
• A maquina pode receber os seguintes tipos de operação:
  • MUDA x A: Para todo nó y, onde y é x ou y está contido na subárvore de x, faça V_y = V_y XOR A
  • SOMA x: Retorna a soma de todos os valores da subárvore de x, incluindo o mesmo.

Entrada

A primeira linha da entrada contém dois inteiros N, M (1 <= N, M <= 10⁵) representando a quantidade de nós na arvore e a quantidade de queries respectivamente.

A segunda linha da entrada contém N inteiros A_i (1 <= A_i <= 10⁸)$ onde A_i é o valor inicial presente no nó i da árvore.

As próximas N - 1 linhas contem um par de inteiros A, B cada (1 <= A, B <= N) representando que existe uma ligação os nós A e B.

As próximas M linhas contém uma query cada, podendo ser:

• MUDA x A
• SOMA x

É garantido que o nó x é um nó da arvore e que o valor de A não excede 10⁸.

Saída

Para cada query do tipo SOMA x, você deverá imprimir uma linha contendo soma de todos os valores no momento da subárvore de x, incluindo o mesmo.

Exemplo

Entrada:
4 3
1 2 3 4
2 1
3 1
4 3
SOMA 1
MUDA 3 10
SOMA 1

Output:
10
26