Bạn được cho một đồ thị liên thông có ~V~ đỉnh và ~V-1~ cạnh, với mỗi đỉnh sẽ có một trọng số tương ứng (các đỉnh khác nhau có thể có trọng số bằng nhau). Lần này, ~w~ có một số thao tác trên cây muốn nhờ bạn xử lí như sau:

• ~1~ ~u~ ~v~: hỏi trọng số bé nhất trong số các đỉnh trên đường đi từ ~u~ đến ~v~.
• ~2~ ~u~ ~v~: hỏi trọng số lớn nhất trong số các đỉnh trên đường đi từ ~u~ đến ~v~.
• ~3~ ~u~ ~v~: đảo ngược trọng số các đỉnh trên đường đi từ ~u~ đến ~v~.

Giả sử các đỉnh trên đường đi từ ~u~ đến ~v~ lần lượt là: ~u~, ~u_{1}~, ~u_{2}~, ~u_{3}~, ~\dots~ ~u_{k}~, ~v~.

Trọng số tương ứng là: ~w_{u_1}~ ~w_{u_2}~ ~w_{u_3}~ ...~w_{u_k}~ ~w_{v}~.

Thì sau khi thực hiện thao tác loại ~3~ trọng số các đỉnh sẽ trở thành ~w_{v}~ ~w_{u_k}~ ...~w_{u_2}~ ~w_{u_1}~ ~w_{u}~.

Input

Dòng đầu tiên chứa ~2~ số tự nhiên ~V~ và ~Q~ - số đỉnh của đồ thị và số truy vấn.

Dòng tiếp theo chứa ~V~ số tự nhiên là trọng số của các đỉnh ~1~, ~2~, ~3~, ..., ~V~.

~V-1~ dòng tiếp theo mỗi dòng chứa ~2~ số tự nhiên ~u~ ~v~ - có cạnh nối từ ~u~ đến ~v~.

~Q~ dòng tiếp theo mỗi dòng là một trong ~3~ loại truy vấn nêu trên.

Output

Với mỗi truy vấn loại 1 và 2 in ra một dòng tương ứng chứa kết quả truy vấn đó.

Giới hạn

• Trong tất cả các test: ~V~, ~Q \leq 10^{5}~, trọng số các đỉnh ~\leq 10^{9}~.
• Trong 20% các test: ~V~, ~Q \leq 10^{3}~.
• Trong 40% các test tiếp theo: số lượng truy vấn loại "3 ~u~ ~v~" ~\leq 100~.

Sample Input

8 4
2 4 1 4 7 5 2 3
1 2
1 3
2 4
2 5
3 6
3 7
3 8
2 6 4
1 4 1
3 7 2
1 6 8

Sample Output

5
2
2