Giải bài trực tuyến

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₁, u_2, u_3,... u_k, v.

Trọng số tương ứng là: w_u,  w_u1,  w_u2, w_u3,... w_uk, 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_uk,... w_u2, w_u1, 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.

Giới hạn

• Trong tất cả các test: V,Q ≤ 10⁵, trọng số các đỉnh ≤ 10⁹.
• Trong 20% các test: V,Q ≤ 10³.
• Trong 40% các test tiếp theo: số lượng truy vấn loại "3 u v" ≤ 100.

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 đó.

Example

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

Output

5
2
2