This page is still under construction.

Parts of this page are still being built. What you see may change.

League

Interview

Time limit1sMemory limit128 MB

Summary
Given every match result in a round-robin soccer league, compute each team's total points and print its rank, where tied teams share the best rank.
Level

Easy2 of 10

Topics
Implementation, Array, Sorting, Simulation
Solved
No attempts yet

Problem

A soccer league has NN teams, numbered from 11 to NN. In this league every pair of distinct teams plays exactly once, so a total of N(N−1)/2N(N-1)/2 matches are played.

In each match, the team that scores more goals wins. Points are awarded as follows:

  • Winning team: 33 points
  • Losing team: 00 points
  • Draw: each team gets 11 point

The league standings are determined solely by the total number of points each team has earned; goal difference is not considered. Teams with the same total share the same rank, and that rank is the highest possible value. In other words, a team's rank equals (the number of teams with strictly more points) + 1+\, 1.

For example, suppose 44 teams take part in the league, so 4(4−1)/2=64(4-1)/2 = 6 matches are played. Suppose the results are as in the table below. In each cell, the number to the left of the hyphen (-) is the score of the team in that row, and the number to the right is the score of the team in that column.

Team 1Team 2Team 3Team 4WDLPts
Team 1---0 - 12 - 12 - 21114
Team 21 - 0---1 - 13 - 02107
Team 31 - 21 - 1---1 - 30121
Team 42 - 20 - 33 - 1---1114

Team 2 has the most points and is ranked 11st. Team 1 and Team 4 have the next-highest and equal totals, so both are ranked 22nd. Team 3 has the fewest points and is ranked 44th.

Given the results of all matches, write a program that computes the rank of each team.

Input

The first line contains the number of teams NN (2≤N≤1002 \le N \le 100).

Each of the next N(N−1)/2N(N-1)/2 lines contains the result of one match as four integers AA BB CC DD, meaning that in the match between team AA and team BB, team AA scored CC points and team BB scored DD points. AA and BB are always different, and the result of the same match is never given more than once.

Output

Print NN lines. The ii-th line contains the rank of team ii.

Examples2

  1. Example 1

    Input
    4
    1 2 0 1
    1 3 2 1
    1 4 2 2
    2 3 1 1
    2 4 3 0
    3 4 1 3
    
    Expected output
    2
    1
    4
    2
    
  2. Example 2

    Input
    5
    1 2 1 1
    3 4 3 1
    5 1 1 2
    2 3 0 0
    4 5 2 3
    1 3 0 2
    5 2 2 2
    4 1 4 5
    3 5 4 0
    2 4 0 1
    
    Expected output
    2
    4
    1
    4
    3