Задача Foxtrot

Описание

You may heard about such unusual type of sport like dancesport. If say shortly, there are couples, they dance dances (usually 5) and there are, of course, judges (always an odd number), which score dances, danced by couples. Because the number of couples could be very large, there maybe several rounds in a competition. The scoring is regulated by so called The Skating System . We are not interested in preliminary rounds, because they are quite easy from view of scoring. The most interesting and complicated one is the final round. There maybe at most 8 couples in the final round. The final placing in each dance is determined using following rules.

Rule 1 is about preliminary rounds. Rules 2, 3, 4 apply specifically to the competition judges.

Rule 2. In a final round all couples must receive a placement from each judge.

Rule 3. In a final round a judges first choice is marked 1 , second choice is marked 2 , third choice is marked 3 , and so on.

Rule 4. In a final round a judge may not tie any couple for any place of any dance

Rules 5, 6, 7, and 8 apply to tabulating the results for the individual dances in a section or for a single-dance section.

Rule 5. How to allocate positions in each dance

The Skating System is based on the marks a couple receives from a majority of judges. The first and simplest step is to ascertain what makes up a majority. The next step is to place the winner by inspecting the marks for the number of 1st places. It is important to note that in this rule we simply count the number of places, we do not add them together. The couple who has received the majority of 1st place marks is the winner of that dance and their marks have no further impact on the tabulation process. The next step is to determine who is to be placed second. This follows a similar process. In this case, however, we count the number of 2nd place and higher marks for the remaining couples. The next step is to determine who is to be placed third. We, similarly, count the number of 3rd place and higher marks for each of the remaining couples. This process is repeated until all couples have been placed.

Rule 6. More than one couple have a majority for the same place.

Rule 6 is a simple follow-on to Rule 5. The position is allocated according to which couple has the greater majority. All couples with the majority are placed before you consider the remaining couples.

Rule 7. If two or more couples have an equal majority for the same position

Now is the time to add together the place-marks and not just count them. Add (not count!) the place-marks for each couple that has the majority. The couple with the lowest total (sum) is awarded the position. This process continues until all couples with the equal majority have been awarded positions. OK! Next question, "Same majority, same sum...?" The last part of Rule 7 defines a tie. There are situations where no matter how many rules you apply you cannot separate the couples. In the event of two couples having an equal majority and also an equal sum, we go to the next order of scores, FOR THESE COUPLES ONLY. If the next order still gives us an equal majority and sum we go to the next one, and the next until we reach the last possible. For 6 couples this will be 6th and higher, for 7 couples 7th and higher, and for 8 couples 8th and higher. Remember that if you have more than 8 couples you will not be running a final! If we still have a tie at the last order of scores then each couple is awarded the highest of the positions that we are working with. For example, if we have two couples and we are looking to place 3rd and 4th each couple will be awarded the 3rd position. Note, that in this case there no couple will be on the 4th place.

Rule 8. If no couple receives a majority for the position under review.

After Rule 7, Rule 8 is simplicity itself. If no couple achieves a majority of 1st place marks then you move on to the 2nd place and higher . If there is no majority there you continue onto the next and the next until one or more couples achieve a majority.

You are given the places which were given by each judge to each couple in Foxtrot. Output final results of Foxtrot.

Формат входных данных

The first line of the input file contains two integer numbers N - the number of couples and M - the number of judges ( 1 <= N <= 8, 1 <= M <= 13, M is odd ). Each of the next N lines contains M + 1 numbers. First number in each line - the couple number (positive integer not larger than 1000 ), next M numbers are integers from interval 1..N - the places, each judge has given to the couple. It's guaranteed that given results are correct according to rules 2, 3, 4 . Numbers in each line are separated with spaces.

Формат выходных данных

Output N lines, containing two integers each - the number of couple and its place, separated with a space. Output couples in order from highest place to lowest. In case when two couples share a place output them in increasing order of their numbers.