favorite We need a little bit of your help to keep things running, click on this banner to learn more

2013 Petrozavodsk, February 2


Four teams are taking part in football tournament. During this tournament, each team must play one game against every other team. Some of the games have already been played and the results are known. Your task is to determine the possible outcomes of the tournament, assuming that remaining games could have any result (each team can score any non-negative integer number of goals).

After each game, the winning team gets three points and the losing team gets zero points. In case of a draw, both teams get one point. The teams are ranked according to the sum of their points. If two teams have the same number of points, they are ranked by the difference between scored goals s and conceded goals c (the more is s − c, the better the rank). If the values of s − c are also the same, teams can be ranked either way due to other tie-breaking factors. In the end, each team gets a distinct rank from 1 to 4. Two outcomes of the tournament are different if there is a team which is ranked differently in these outcomes.


The first line contains the number n (0 n 6) of games already played. Next n lines describe these games. Each game is described by integers a, b, c, d where a and b are the numbers of teams, and c, d are the number of goals scored by team a and team b respectively (1a < b4; 0c, d10). It is guaranteed that no two teams played more than one game against each other.


On the first line output the number m of different possible tournament outcomes. Each of the next m lines should contain four integers: the numbers of teams which get ranks 1, 2, 3 and 4 respectively. The outcomes should be listed in lexicographical order.

Time limit 1 second
Memory limit 64 MiB
Input example #1
1 2 1 0
1 3 2 1
1 4 3 2
2 3 1 0
2 4 5 4
Output example #1
1 2 3 4
1 2 4 3

Example description: The first team got nine points, and the second team got six points. The team that wins the last game gets three points and takes the third place. In case of a draw, teams 3 and 4 can be ranked either as 3-rd and 4-th respectively or vice versa.

Author M.Rubinchik, D.Dublennykh
Source 2013 Petrozavodsk, Winter, Ural FU contest, Kontur Cup, Problem G