ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural FU contest. Kontur Cup. Petrozavodsk training camp. Winter 2013

About     Problems     Submit solution     Judge status     Standings
Contest is over

G. Mundial

Time limit: 1.0 second
Memory limit: 64 MB
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 sc, the better the rank). If the values of sc 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.

Input

The first line of input contains an integer n: the number of games already played (0 ≤ n ≤ 6). 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 (1 ≤ a < b ≤ 4; 0 ≤ c, d ≤ 10). It is guaranteed that no two teams played more than one game against each other.

Output

On the first line output an integer m: the number 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.

Sample

inputoutput
5
1 2 1 0
1 3 2 1
1 4 3 2
2 3 1 0
2 4 5 4
2
1 2 3 4
1 2 4 3

Notes

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.
Problem Author: Mikhail Rubinchik (prepared by Denis Dublennykh)
Problem Source: Ural FU contest. Kontur Cup. Petrozavodsk training camp. Winter 2013
To submit the solution for this problem go to the Problem set: 1957. Mundial