Monocarp plays a computer game. In this game, he maintains a space empire. The empire is governed by \(n\) political parties. Initially, every party has political power equal to \(0\), and there is no ruling party.
During each of the next \(m\) turns, the following happens:
- initially, Monocarp has to choose which party he supports. He can support any party, except for the ruling party. When Monocarp supports a party, its political power is increased by \(1\). If Monocarp supports the \(i\)-th party during the \(j\)-th turn, his score increases by \(a_{i,j}\) points;
- then, the elections happen, and the party with the maximum political power is chosen as the ruling party (if there are multiple such parties, the party with the lowest index among them is chosen). The former ruling party is replaced, unless it is chosen again;
- finally, an event happens. At the end of the \(j\)-th turn, the party \(p_j\) must be the ruling party to prevent a bad outcome of the event, otherwise Monocarp loses the game.
Determine which party Monocarp has to support during each turn so that he doesn't lose the game due to the events, and the score he achieves is the maximum possible. Initially, Monocarp's score is \(0\).
Output
If Monocarp loses the game no matter how he acts, print one integer \(-1\).
Otherwise, print \(m\) integers \(c_1, c_2, \dots, c_m\) (\(1 \le c_j \le n\)), where \(c_j\) is the index of the party Monocarp should support during the \(j\)-th turn. If there are multiple answers, print any of them.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 3
2 1 2
1 2 3
4 5 6
|
2 1 2
|
|
2
|
3 5
1 1 1 2 1
1 1 1 1 1
10 5 7 8 15
7 10 9 8 15
|
1 3 2 2 1
|
|
3
|
3 5
1 1 1 1 1
1 1 1 1 1
10 5 7 8 15
7 10 9 8 15
|
-1
|