가혹한 국경

유럽 연합의 회원국들은 임의의 두 국가 사이에 정확히 하나의 경로가 있는 그래프, 즉 트리로 볼 수 있습니다. 국가에는 1부터 $n$까지 번호가 붙어 있고, 크로아티아는 1번입니다. 올해는 Malnar 씨가 유럽 연합의 의장을 맡아 회의를 많이 열어야 합니다. 각국 대표들은 독특하게도 무리를 지어 이동하는 것을 좋아합니다. 크로아티아로 가는 길에 어떤 국가를 지나는 사람은 모두 먼저 그 국가에 모입니다. 그다음 그 국가의 대표와 함께 한 무리가 되어 다음 국가로 이동합니다. 다음 국가에서는 또 사람들이 합류하며, 모두가 1번 노드에서 만날 때까지 이 과정이 반복됩니다. (자세한 내용은 첫 번째 입력 예시의 설명을 참고하십시오.)

유럽 연합에는 사람에게 부과하는 관세가 새로 도입되었습니다. 각 국가 $i$에는 관세 $c_i$가 정해져 있으며, 그 나라에 들어가는 사람은 누구나 이 금액을 내야 합니다. 다만 대표는 자기 나라에서는 관세를 내지 않습니다. 세관원들은 연합의 취지에 냉소적입니다. 각 국가에서는 함께 들어오는 무리 가운데 가장 큰 무리에게 관세의 두 배를 부과합니다. 가장 큰 무리가 여러 개라면 출발한 국가의 번호가 가장 작은 무리에게 부과합니다.

프로그램은 다음 세 가지 연산을 처리해야 합니다.

• $1$ $v$: 지금 회의가 열린다면 국가 $v$의 대표가 얼마를 내야 하는지 구합니다.
• $2$ $v$ $c$: 국가 $v$의 관세를 $c$로 바꿉니다.
• $3$ $v$ $c$: 새로운 국가가 생깁니다. 새 국가의 번호 $k$는 아직 존재하지 않는 가장 작은 자연수입니다. 이 국가의 관세는 $c$이며, 국가 $v$와 연결됩니다.

첫 줄에 $n$과 $q$($1 \le n, q \le 10^5$)가 주어집니다. 이는 처음 국가의 수와 연산의 수입니다. 둘째 줄에는 $n$개의 정수가 주어지며, $i$번째 정수는 국가 $i$의 관세 $c_i$($0 \le c_i \le 10^9$)입니다. 이어지는 $n-1$개의 줄에는 $u_i$와 $v_i$($1 \le u_i, v_i \le n$, $u_i \ne v_i$)가 주어지며, 국가 $u_i$와 국가 $v_i$가 간선으로 연결되어 있다는 뜻입니다.

$lastans$는 가장 최근 1번 연산의 답입니다. 1번 연산이 한 번도 없었다면 $lastans = 0$입니다. $k$는 지금까지 나타난 가장 큰 국가 번호입니다. $\oplus$는 비트 xor 연산을 뜻합니다.

$i$번째 사건이 1번 연산이면 한 줄에 $1$ $v'$($0 \le v' \le 10^{18}$, $1 \le v \le k$)가 주어지며, $v = v' \oplus lastans$입니다.

$i$번째 사건이 2번 또는 3번 연산이면 $2$ $v'$ $c'$ 또는 $3$ $v'$ $c'$($0 \le v', c' \le 10^{18}$, $1 \le v \le k$, $0 \le c \le 10^9$)가 주어지며, $v = v' \oplus lastans$, $c = c' \oplus lastans$입니다.

$i$번째 줄에 $i$번째 1번 연산의 답을 출력합니다.

첫 번째 입력의 설명: 네 번째 연산이 처음 등장하는 1번 연산이므로 $lastans = 0$이며, 이 연산은 아무것도 바꾸지 않습니다. 국가 2의 대표는 국가 3으로 이동하면서 두 배의 관세 6을 냅니다. 이 무리가 그 도시에 들어가는 유일한 무리이므로 가장 큰 무리이기도 합니다. 이제 국가 2와 3의 대표가 함께 국가 6으로 들어갑니다. 이 무리는 두 명이고 국가 7에서 온 무리는 한 명뿐이므로, 두 배의 관세를 내는 쪽은 국가 2의 대표이며 관세 6을 냅니다. 그 뒤 국가 2, 3, 6, 7의 대표가 함께 국가 1로 이동하고, 가장 큰 무리로서 두 배의 관세를 냅니다. 국가 2의 대표는 8을 냅니다. 합계는 $6 + 6 + 8 = 20$입니다.

다섯 번째 연산에서는 $lastans = 20$이므로 $v = 16 \oplus 20 = 5$입니다. 국가 5의 대표는 혼자 국가 1로 이동합니다. 가장 큰 무리가 아니므로 일반 관세 $4$를 냅니다.