Sau khi kết thúc giải bóng đá vô địch quốc gia ở đất nước XYZ, các đội bóng tham dự giải sẽ được Liên đoàn bóng đá xếp hạng dựa trên kết quả các trận đã thi đấu.
Ở mỗi trận đấu, đội thắng sẽ được ~3~ điểm, thua không có điểm và hòa thì mỗi đội được ~1~ điểm.
Việc xếp hạng các đội theo quy tắc sau:

• Các đội được xếp giảm dần theo tổng điểm đạt được ở các trận đấu của giải, nghĩa là đội có tổng điểm cao hơn được xếp hạng cao hơn.
• Nếu tất cả các đội có điểm bằng nhau, thì việc sắp xếp dựa theo các tiêu chí phụ sau:
  • Tiêu chí thứ nhất: So sánh hiệu số bàn thắng bại, đội nào có hiệu số bàn thắng bại nhiều hơn thì xếp hạng cao hơn.
  • Tiêu chí thứ hai: Nếu hiệu số bàn thắng bại bằng nhau, so sánh số bàn thắng, đội nào ghi được nhiều bàn thắng hơn thì xếp hạng cao hơn.
  • Tiêu chí thứ ba: Nếu vẫn có môt số đội bằng nhau ở hai tiêu chí trên thì đội có số thứ tự nhỏ hơn sẽ được xếp hạng cao hơn.
• Nếu chỉ có một số đội có điểm bằng nhau, thì xem như có một giải đấu mới cho các đội bằng điểm. Tổng điểm và các tiêu chí phụ được tính theo kết quả các trận đấu giữa các đội này ở giải ban đầu. Sau đó áp dụng quy tắc xếp hạng đã nêu trên cho các đội ở giải đấu mới này.

Yêu cầu:

Xác định bảng xếp hạng các đội bóng đã tham dự giải vô địch quốc gia.

Dữ liệu vào:

• Dòng đầu chứa ~2~ số ~N~ và ~K~ ~(1 \leq N \leq 100, 1 \leq K \leq 1000)~, là số đội bóng và số trận đấu. Các đội được đánh số từ ~1~ đến ~N~.
• ~K~ dòng tiếp theo, mỗi dòng có dạng '~A~ ~B~ ~C~ : ~D~', mô tả kết quả trận đấu giữa hai đội ~A~ và ~B~ có tỉ số là ~C:D~ ~(0 \leq C, D \leq 9)~.

Kết quả ra:

Gồm một dòng chứa bảng xếp hạng các đội bóng theo thứ tự từ đội có hạng cao nhất đến đội có hạng thấp nhất.

Sample Input

5 4 
1 5 1:0 
2 3 2:1 
3 4 3:0 
4 5 1:1

Sample Output

2 3 1 5 4