EIU Programming Practices and Exams

An được phân công thống kê thu nhập ở một số ngôi làng. Biết thu nhập của từng người và mối quan hệ cùng làng giữa mọi người, hãy cho biết thu nhập cao nhất, thấp nhất và trung bình của mỗi ngôi làng. Lưu ý mỗi người chỉ thuộc về đúng một làng; a_x0 và a_xk cùng làng khi và chỉ khi  a_xi và a_x(i+1) cùng làng với mọi i từ 0 đến (k-1)

Input

Dòng đầu tiên là số nguyên n là người dân (1 ≤ n ≤ 10⁵) và số mối quan hệ cùng làng m (1 ≤ m ≤ 10⁵).

Dòng tiếp theo gồm n số nguyên từ a_i (0 ≤ a_i < N) là thu nhập của n người (từ người 0 đến người n – 1).

M dòng tiếp theo, mỗi dòng gồm hai số nguyên a, b thể hiện rằng người a và b số cùng làng.

Output

Với mỗi làng, hãy xuất ra người đại diện, thu nhập cao nhất, thấp nhất và trung bình. Thu nhập trung bình được làm tròn tới hàng đơn vị. Người đại diện của làng là người có chỉ số nhỏ nhất trong làng.

Các làng được xuất ra theo thứ tự người đại diện tăng dần .

Example

Input:
5 3
3 2 5 4 6
0 1
2 3
2 4


Output:
0 3 2 3
2 6 4 5