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.

EIGROUPSC - Average score

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 * 105). Each person is numbered from 0 to n - 1.

The ith real number in the next line represents the score of the ith 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

Output

5 4

9.2 8.3 8.4 5.6 7.2

1 2

2 4

4 1

0 3

9.2 5.6

8.4 7.2


Added by:Ha Minh Ngoc
Date:2021-03-17
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: GOSU
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.