Given a connected tree with N nodes numbered through 1 to N, each node has an 31-bit integer value associated with it. You are given Q queries and there are two types of queries. type 1: 1 u v flip the bits of node values on the path from u to v including u and v. type 2: 2 u v find the sum of node values on the path from u to v including u and v.

Input Format

First line containing two space seperated integers. First is N i.e. number of nodes. Second is Q i.e. number of queries. Next N-1 lines contains two space seperated integers u and v denoting an edge between node u and node v. Next line contains N space seperated integers denoting node value[i]. Next Q lines contains three space seperated integers type u v denoting the query.

Output Format

For each query of type 2 output a single singe containing the answer to the query.

Contraints

1

Sample 0

Input

5 3 1 2 2 3 3 4 4 5 1 2 1 2 2 2 1 5 1 2 3 2 2 3

Output

8 4294967291

Given a connected tree with N nodes numbered through 1 to N, each node has an 32-bit integer value associated with it. You are given a queries and there are two types of queries. type 1: 1 u v flip the bits of node values on the path from u to v including u and v. type 2: 2 u v find the sum of node values on the path from u to v including u and v. Input Format First line containing two space seperated integers. First is N i.e. number of nodes. Second is e i.e. number of queries . Next N-1 lines contains two space seperated integers u and v denoting an edge between node u and nodev. Next line contains N space seperated integers denoting node value[i]. Next lines contains three space seperated integers type u v denoting the query. Output Format For each query of type 2 output a single singe containing the answer to the query. Contraints 1