VMWTREE - Lại là cây khung

Giới hạn

• Thời gian: 5.0s
• Bộ nhớ: 1536MB
• Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

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

---

• Người up: voj