The countries of the European Union can be imagined as a graph where there is exactly one path between any two countries, i.e., a tree. The countries are labeled with numbers from $1$ to $n$, with Croatia labeled as $1$. Since Mr. Malnar is presiding over the European Union this year, many meetings need to be organized. The representatives of the countries are peculiar and love to travel in groups. Therefore, when traveling to Croatia, all those who pass through a particular country on their journey will first meet in that country and then continue their journey as a group together with the representative of that country to the next country, where they will join with even more representatives until they all meet at the meeting in node $1$. (For a more detailed explanation, see the explanation of the first example.)

Unfortunately, a customs duty on people has been introduced among the European Union countries! For each country, its customs duty $c_i$ is known, and every person must pay this price when entering the country; naturally, the country's representatives do not pay the customs duty in their own country. However, the customs officers are cynical about the whole idea of the European Union, so in each country, they have decided to charge double the price to the largest group of people arriving together. If there are multiple equally large groups, they will charge the one coming from the country with the smallest label. Changes in the European Union are turbulent, so Mr. Malnar has asked you to support three key operations:

1 $v$ - if a meeting were held at this moment, how much money would the representative of country $v$ have to pay? 2 $v$ $c$ - country $v$ changes its customs duty to $c$. 3 $v$ $c$ - a new country with label $k$ has appeared, where $k$ is the smallest natural number such that no country with that label exists, which has customs duty $c$ and is connected to country $v$.

Mr. Malnar is lost among all his obligations and asks you to create a program that can quickly answer these questions. The next two weeks are crucial!

Input

The first line contains numbers $n$ and $q$ ($1 \le n, q \le 10^5$), which denote the initial number of countries and the number of operations.

The next line contains $n$ numbers, where the $i$-th number denotes $c_i$ ($0 \le c_i \le 10^9$), the customs duty of the $i$-th country.

The next $n - 1$ lines contain numbers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), which denote that countries $u_i$ and $v_i$ are connected by an edge.

Let $lastans$ denote the answer to the last operation of type 1 at any given moment, or $lastans = 0$ if there have been no operations of type 1. Let $k$ be the largest label of any country up to that moment. Let $\oplus$ denote the bitwise XOR operation.

If the $i$-th event is of type 1, the line contains numbers $1$ $v'$ ($0 \le v' \le 10^{18}, 1 \le v \le k$) and $v = v' \oplus lastans$.

If the $i$-th event is of type 2, the line contains numbers $2$ $v'$ $c'$ ($0 \le v', c' \le 10^{18}, 1 \le v \le k, 0 \le c \le 10^9$) and $v = v' \oplus lastans, c = c' \oplus lastans$.

If the $i$-th event is of type 3, the line contains numbers $3$ $v'$ $c'$ ($0 \le v', c' \le 10^{18}, 1 \le v \le k, 0 \le c \le 10^9$) and $v = v' \oplus lastans, c = c' \oplus lastans$.

Output

You must print the answer to the $i$-th operation of type 1 on the $i$-th line.

Examples

Input 1

7 5
4 6 3 4 0 5 9
2 3
3 6
4 1
5 1
1 6
7 6
2 5 0
2 6 3
3 5 4
1 2
1 16

Output 1

20
4

Note 1

Explanation of the first example: Since only the fourth operation is the first of type 1, $lastans = 0$ and the operation is not changed. The representative of country 2 travels to country 3 and pays double the customs duty of 6 because they are the only ones and therefore the largest group entering that city. Now, the representatives from cities 2 and 3 enter city 6 together; because this group consists of two people, and the group from node 7 consists of only one person, they pay double the customs duty, i.e., the representative of city 2 pays 6. After that, the representatives of countries 2, 3, 6, and 7 travel to country 1 together and again pay double the customs duty as the largest group, so the representative of country 2 pays 8. This makes a total sum of $6 + 6 + 8 = 20$.

In the fifth operation, $lastans = 20$, so $v = 16 \oplus 20 = 5$. The representative of country 5 travels to country 1 alone; because they are not the largest group, they pay the single customs duty, i.e., 4.

Input 2

5 5
6 2 2 7 5
1 3
2 3
3 5
5 4
3 1 0
1 6
1 4
2 10 11
1 10

Output 2

6
14
26