EIU Programming Practices and Exams

Mùa Asian Cup đang diễn ra, sẽ có nhiều trận đấu giữa các đội bóng với nhau để quyết định ngôi vô địch. Để giúp các HLV có thể dự đoán được khả năng thắng của đội bóng mình. Ban tổ chức muốn nhờ sinh viên của EIU giúp đỡ. Mỗi đỉnh là 1 đỉnh trong đồ thị gồm n đỉnh với mỗi cạnh là một trận đấu của hai đội. Mỗi đội có giá trị P thể hiện mức độ mạnh hoặc yếu của đội bóng. Mỗi cạnh đại diện cho trận đấu giữa hai đội bóng. Một đội bóng được cho là có khả năng thắng, khi độ chênh lệnh giá trị giữa đội bóng đó với đội đối phương, không vượt quá một số K.

Input

Dòng đầu tiên gồm hai số nguyên N và M  tương ứng là số đỉnh và số cạnh đồ thị. Đỉnh của đồ thị được đánh số từ 0 tới N.

Dòng tiếp theo gồm N giá trị P_i, giá trị thứ i tương ứng là mức độ của đỉnh thứ i.

M dòng tiếp theo, mỗi dòng gôm hai số u và v, thể hiện trận đấu giữa u và  v.

Một số nguyên K, thể hiện độ chênh lệnh tối đa mà một đội bóng có thể thắng đối thủ.

Output

Với mỗi đội bóng, xuất ra chỉ số đỉnh, số trận đội đó có khả năng thắng. Các đỉnh được xuất ra theo thứ tự từ nhỏ đến lớn.

Example

Input:
5 7
3 9 7 2 1
0 1
1 3
1 2
2 3
3 4
0 2
5

Output:
0 1
1 1
2 3
3 2
4 1