Bedao tổ chức một giải đấu bóng đá với sự tham gia của nhiều đội trên cả nước. Trong danh sách có ~n~ đội bóng, mỗi đội gặp nhau đúng ~2~ lần trong một mùa giải và có tất cả ~n \times (n-1)~ trận đấu, khi chưa có trận đấu nào diễn ra (vòng ~0~) thì đội thứ ~i~ sẽ xếp thứ hạng ~a_i~ trên bảng xếp hạng (biết rằng bảng xếp hạng ban đầu này được xếp theo thứ tự từ điển qua tên các đội bóng), ta có thể xem đây là tên của đội bóng thứ ~i~.
Cách phân hạng của giải đấu như sau:
- Một trong hai đội thắng sẽ đạt được ~3~ điểm.
- Hai đội hòa nhau thì mỗi đội sẽ đạt được ~1~ điểm.
- Một trong hai đội thua sẽ không có điểm.
Với ~Pts~ là số điểm đạt được của đội bóng, ~GD~ là hiệu số bàn thắng ghi được và số bàn bị thủng lưới của đội bóng. Biết rằng, đội ~a_i~ xếp hạng cao hơn đội ~a_j~ khi:
- ~Pts~ đội ~a_i~ phải lớn hơn đội ~a_j~.
- Nếu ~Pts~ hai đội bằng nhau thì ~GD~ đội ~a_i~ phải lớn hơn đội ~a_j~.
- Nếu ~GD~ hai đội bằng nhau thì đội ~a_i~ phải có số bàn thắng nhiều hơn đội ~a_j~.
- Nếu số bàn thắng hai đội vẫn bằng nhau thì hai đội sẽ xếp chung một hạng trên bảng xếp hạng.
Để tổ chức một giải đấu tầm cỡ quốc gia như thế, Bedao phải thiết kế một bảng xếp hạng sao cho mọi người có thể dễ dàng theo dõi nhất, nhưng kinh phí thì có hạn cho nên bảng xếp hạng của giải chỉ gồm thông tin của đội vô địch, với cách làm này Bedao cũng sẽ đỡ phải thưởng tiền cho những đội xếp sau.
Yêu cầu: in ra danh sách đội vô địch (xếp thứ ~1~) sau ~n \times (n-1)~ trận đấu.
Input
- Dòng đầu tiên chứa số nguyên dương ~n~ ~(2 \leq n \leq 20)~ là số đội tham dự giải đấu.
- Dòng thứ hai chứa các số ~a_1, a_2, \dots, a_n~ ~(1 \leq a_i \leq n)~ là thứ hạng của các đội ở vòng ~0~, khi ở vòng này thì thứ hạng đội được xếp theo thứ tự từ điển theo tên đội và các phần tử ~a_1, a_2, \dots, a_n~ đôi một phân biệt nhau.
- ~n \times (n-1)~ dòng tiếp theo là thông tin các trận đấu diễn ra ở giải đấu, thông tin có dạng là: ~a_i~ ~a_j~ ~x~ ~y~ ~(0 \leq x,y \leq 30)~. Biết rằng ~a_i~ là thứ hạng ở vòng ~0~ của đội bóng thứ ~i~, ~a_j~ là thứ hạng ở vòng ~0~ của đội bóng thứ ~j~, ~x~ là số bàn ghi được của đội bóng thứ ~i~, ~y~ là số bàn ghi được của đội bóng thứ ~j~.
Output
- Gồm một dòng là danh sách đội vô địch sau giải đấu, danh sách có thể in theo thứ tự bất kỳ và các số nguyên trong danh sách là thứ hạng của đội ở vòng ~0~.
Sample Input 1
4
2 1 3 4
4 2 16 8
1 4 8 16
2 3 29 29
4 3 16 8
1 3 29 29
2 1 29 29
4 3 16 8
4 2 16 8
2 3 29 29
1 4 8 16
1 3 29 29
2 1 29 29
Sample Output 1
4
Sample Input 2
3
3 1 2
1 2 0 0
3 2 1 2
1 3 0 3
2 1 2 1
3 2 2 0
3 1 2 2
Sample Output 2
3
Sample Input 3
3
3 1 2
1 2 0 0
3 2 1 2
1 3 0 3
2 1 6 1
3 2 2 0
3 1 2 2
Sample Output 3
2 3
Bình luận