Byteball Match

Time limit2sMemory limit512 MB

Summary

Given partial results of a round-robin group, list every team that can still finish first once all remaining matches are played, under points and goal-difference tiebreaks.

Level: Hard8 of 10
Topics: Graph, Brute force, Implementation, Sorting
Solved: No attempts yet

Problem

The Bytean national team is competing in the Byteball World Cup. A byteball match lasts 64 minutes, and the team that scores more goals wins. If both teams score the same number of goals, the match is a draw. In a single match each team may score any number of goals.

All teams in the Cup are split into two groups. Within each group the teams play a round-robin tournament, so every team meets each of the other teams exactly once. The winner of a match receives $2$ points and the loser receives none. In a draw each team receives $1$ point. The team with the most points in a group finishes first. If several teams are tied for the most points, the one with the best goal difference (goals scored minus goals conceded) among those tied teams is placed first. If that criterion still leaves a tie, the group winner is chosen at random among the teams that share both the maximum points and the best goal difference. The winners of the two groups meet in the World Cup final.

The Bytean team is the favorite of this World Cup. As expected, it has won every match in its own group and has already secured a place in the final. Meanwhile the matches in the other group are not finished yet, and no team in that group has played all of its matches. The coach of the Bytean team wants to start preparing for the final, but the tactics depend on the opponent, so he would like to know which teams in the other group still have a chance of finishing first. Help him find all such teams.

Input

The first line contains two integers $n$ and $m$ ( $2 \le n \le 100$ , $0 \le m \le \frac{n(n-2)}{2}$ ), the number of teams in the other group and the number of matches already played. Each of the next $m$ lines contains four integers $a_i$ , $b_i$ , $p_i$ , $q_i$ ( $1 \le a_i, b_i \le n$ , $a_i \ne b_i$ , $0 \le p_i, q_i \le 2048$ ), meaning that team $a_i$ played team $b_i$ , and in that match team $a_i$ scored $p_i$ goals while team $b_i$ scored $q_i$ goals.

Output

Print, in increasing order on a single line separated by spaces, the numbers of all teams that still have a chance of finishing first in the group.

Examples1

Example 1

Input

6 9
1 3 10 15
1 4 1 145
1 5 15 112
1 6 24 25
2 3 14 14
2 4 14 15
2 5 14 16
2 6 17 12
3 6 108 107

Expected output

3 4 5