Как известно каждому участнику проекта crowdforces, Тётя Люсине — чуть ли не самый активный человек на земле. Её голова всё время забита какими-то новыми on-ramp задачами. Конечно, даже ей не всегда удаётся придумать что-то хорошее, и в этот раз у неё получилась таска со сказкой, а именно — про таблицы. Ни один ревьювер потом не смог решить эту задачу, а вы сможете?
Дана таблица с \(n\) строками и \(m\) столбцами, где в каждой ячейке написано целое положительное число. Назовём таблицу хорошей, если последовательность чисел в каждой строке является отсортированной в порядке неубывания. Иными словами, для каждого \(1 \le i \le n\) и \(2 \le j \le m\) выполняется следующее условие: \(a_{i,j} \ge a_{i, j-1}\).
Необходимо ровно один раз выбрать столбцы с номерами \(i\) и \(j\) (не обязательно различными), \(1 \le i, j \le m\), и поменять их местами.
Необходимо определить, можно ли после этого получить хорошую таблицу, и вывести соответствующие столбцы, если это возможно.
Выходные данные
Если после перестановки невозможно получить хорошую таблицу, то выведите одно число \(-1\).
В противном случае выведите \(2\) числа — номера столбцов, которые необходимо переставить, чтобы получить хорошую таблицу.
Если существуют несколько решений, выведите любое из них.
Примечание
В первом наборе входных данных таблица уже является хорошей, поэтому мы можем, например, переставить первый столбец с самим собой.
Во втором наборе входных данных нельзя сделать данную таблицу хорошей.
В третьем наборе входных данных необходимо поменять местами первый и второй столбец, тогда таблица станет хорошей.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2 3
1 2 3
1 1 1
2 2
4 1
2 3
2 2
2 1
1 1
2 3
6 2 1
5 4 3
2 1
1
2
|
1 1
-1
1 2
1 3
1 1
|