Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VMWTREE - Lại là cây khung

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, u1, u2, u3,... uk, v.

Trọng số tương ứng là: wu,  wu1,  wu2, wu3,... wuk, wv.

Thì sau khi thực hiện thao tác loại 3 trọng số các đỉnh sẽ trở thành wv, wuk,... wu2, wu1, wu.

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 ≤ 105, trọng số các đỉnh ≤ 109.
  • Trong 20% các test: V,Q ≤ 103.
  • 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

Được gửi lên bởi:VOJ Team
Ngày:2014-08-15
Thời gian chạy:2s-5s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.