Петя — учитель по математике. \(n\) его студентов написали тест, состоящий из \(m\) вопросов. Для каждого студента известно на какие вопросы он ответил верно, а на какие нет.
Если студент правильно ответил на \(j\)-й вопрос, он получает \(p_j\) баллов (иначе он получает \(0\) баллов). Причем баллы за вопросы распределены так, что массив \(p\) является перестановкой чисел от \(1\) до \(m\).
Для \(i\)-го студента Петя знает, что он ожидает получить \(x_i\) баллов за тест. Пете стало интересно, насколько неожиданными могут быть результаты. Петя считает, что неожиданность результатов для студентов равна \(\sum\limits_{i=1}^{n} |x_i - r_i|\), где \(r_i\) — количество баллов, которое \(i\)-й студент получил за тест.
Ваша задача — помочь Пете, найти такую перестановку \(p\), для которой неожиданность результатов максимальна. Если оптимальных ответов несколько, выведите любой из них.
Выходные данные
Для каждого набора входных данных выведите \(m\) целых чисел — перестановку \(p\), для которой неожиданность результатов максимальна. Если оптимальных ответов несколько, выведите любой из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
4 3
5 1 2 2
110
100
101
100
4 4
6 2 0 10
1001
0010
0110
0101
3 6
20 3 15
010110
000101
111111
|
3 1 2
2 3 4 1
3 1 4 5 2 6
|