Màu thống trị trên cây

Cho một cây \(n\) nút, nút thứ \(i\) được tô một màu \(c_i\). Có \(Q\) truy vấn, mỗi truy vấn có dạng \(x, y\): Cần tìm xem trên đường đi đơn từ \(x\) đến \(y\) trên cây, màu nào là màu thống trị. Một màu được gọi là thống trị nếu số lần xuất hiện của nó lớn hơn hẳn tổng số lần xuất hiện của các màu khác (trên đường đi đang xét).

Input

• Dòng đầu chứa hai số nguyên dương: \(n\) \(Q\).

• Dòng thứ hai chứa \(n\) số nguyên: \(c_1\) \(c_2\) \(\ldots\) \(c_n\) (\(1 \leq c_i \leq n\)).

• Mỗi dòng trong số \(n-1\) dòng tiếp theo ghi một cạnh của cây: \(u\) \(v\).

• Mỗi dòng trong số \(Q\) dòng tiếp theo ghi một truy vấn: \(x\) \(y\).

Output

• Với mỗi truy vấn, in ra trên một dòng màu tìm được. Nếu không có màu nào thống trị đường đi đó, in ra \(-1\).

Example

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

-1
1
1
2

Scoring

• Subtask #1 (\(25\%\) số điểm): \(n,Q \leq 1000\).

• Subtask #2 (\(75\%\) số điểm): \(n,Q \leq 250000\).