• محدودیت زمان: ۶ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

Ahlaam is a computer science student, doing her master thesis on a bioinformatics project about MicroRNAs, special molecule types found in cells. During her thesis, she wants to find microRNAs relevant to a specific health factor in human beings.

Ahlaam has designed kk microRNA ranking algorithms, each of which ranks microRNAs from a specific point of view. There are nn microRNAs numbered 11 through nn, and each algorithm produces one permutation of these nn microRNAs. In the permutation produced by each algorithm, the first microRNA is inferred by the algorithm as the most relevant one to the health factor, and the last microRNA is inferred as the least relevant one.

Ahlaam wants to report a consensus ranking on microRNAs. In a consensus ranking, if microRNA ii is ranked before another mircroRNA jj, then at least half of the algorithms should have ranked ii before jj. Write a program to help Ahlaam find a consensus ranking.

ورودی

There are multiple test cases in the input. The first line of each test contains two space-separated integers nn (1n10001 \leq n \leq 1000) and kk (1k2001 \leq k \leq 200), the number of microRNAs and the number of ranking algorithms, respectively. Then, there are kk lines, where the ii-th line contains a permutation of nn numbers 1,,n1, \dots, n, representing the output of the ii-th ranking algorithm. The input terminates with a line containing 00 00 which should not be processed.

خروجی

For each test case, print a single line containing a permutation of nn numbers 1,,n1, \dots , n, representing a possible consensus ranking. If there are more than one correct consensus rankings, print the first one in lexicographic order (a sequence a1,,ana_1, \dots, a_n is lexicographically less than a sequence b1,,bnb_1, \dots, b_n iff there exists a positive integer jj such that ai=bia_i = b_i for all 1ij11 \leq i \leq j - 1 and aj<bja_j \lt b_j ) . If no such a ranking exists, write No solution instead.

مثال

ورودی نمونه ۱

5 3
3 2 4 1 5
4 1 5 2 3
2 4 5 1 3
5 2
5 4 3 2 1
1 2 3 4 5
4 3
1 4 2 3
4 2 3 1
3 1 2 4
0 0
Plain text

خروجی نمونه ‍۱

2 4 1 5 3
1 2 3 4 5
No solution
Plain text

ارسال پاسخ برای این سؤال
فایلی انتخاب نشده است.