Ngan and her friend have just received their study result. Because their class is divided into groups, they want to know the highest score and lowest score of each group. Ngan's friends are in the same group with Ngan. Anyone who is friend of at least one person in the group is also in the same group.

Input

• The first line contains ~2~ integers ~n, m~ denotes the number of people and the number of friendships ~(0 ≤ n, m ≤ 2 \times 10^5)~. Each person is numbered from ~0~ to ~n - 1~.
• The ~i^{th}~ real number in the next line represents the score of the ~i^{th}~ person.
• Each line in the next ~M~ lines contains two numbers ~u~ and ~v~, denoting ~u~ and ~v~ as friends.

Output

• For each group, ordered in ascending of representative (the smallest index in the group), print out the highest score and lowest score.

Sample Input

5 4
9.2 8.3 8.4 5.6 7.2
1 2
2 4
4 1
0 3

Sample Output

9.2 5.6
8.4 7.2