Это интерактивная задача.
Вам дана сетка из \(n\) строк и \(m\) столбцов. Вам нужно заполнить каждую ячейку уникальным целым числом от \(1\) до \(n \cdot m\).
После заполнения сетки вы сыграете с интерактором в игру на этой сетке. Игроки по очереди выбирают из сетки ранее не выбранные ячейки, причем интерактор ходит первым.
В первый ход интерактор может выбрать любую ячейку из сетки. После этого любая выбранная клетка должна быть соседней по стороне хотя бы с одной ранее выбранной клеткой. Игра продолжается до тех пор, пока не будут выбраны все клетки.
Ваша цель состоит в том, чтобы сумма чисел в выбранных вами клетках была строго меньше суммы чисел в клетках, выбранных соперником.
Протокол взаимодействия
Сначала выведите \(n\) строк, каждая из которых содержит по \(m\) целых чисел — числа, которыми вы заполнили сетку. Каждое целое число от \(1\) до \(n \cdot m\) должно появиться ровно один раз.
Затем начинается игра. Интерактор и вы по очереди выводите координаты выбранных ячеек в течение \(n \times m\) ходов, причем интерактор начинает первым.
В свой ход каждый игрок (либо вы, либо интерактор) выводит два целых числа \(i\) и \(j\) (\(1 \le i \le n\), \(1 \le j \le m\)), означающие, что игрок выбрал клетку в \(i\)-й строке и \(j\)-м столбце. Эта клетка не должна быть выбрана в предыдущих раундах. Кроме того, если это не первый ход, клетка должна быть смежной по стороне хотя бы с одной ранее выбранной клеткой.
Если любой из ваших выводов некорректен, жюри выведет «-1», и вы получите вердикт Неправильный ответ.
После всех \(n \cdot m\) ходов, если сумма чисел в выбранных вами клетках не будет строго меньше суммы чисел в клетках, выбранных соперником, жюри выведет «-1» и вы получите вердикт Неправильный ответ.
Если ваша программа получила вердикт Неправильный ответ, она должна немедленно завершиться. В противном случае вы можете получить любой вердикт, так как программа продолжит чтение из закрытого потока.
После вывода не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
- fflush(stdout) или cout.flush() в C++;
- System.out.flush() в Java;
- flush(output) в Pascal;
- stdout.flush() в Python;
- смотрите документацию для других языков.
Взломы в этой задаче отключены.
Примечание
Обратите внимание, что это пример игры и не обязательно представляет собой оптимальную стратегию для обоих игроков.
Сначала мы заполнили сетку \(4 \times 4\) различными целыми числами от \(1\) до \(16\) следующим образом:
| \(2\) | \(3\) | \(4\) | \(10\) |
| \(12\) | \(6\) | \(11\) | \(15\) |
| \(5\) | \(13\) | \(16\) | \(8\) |
| \(9\) | \(7\) | \(1\) | \(14\) |
Далее началась игра.
- Сначала соперник выбирает клетку \((3, 4)\), в которой находится число \(8\). Во время первого раунда интерактор может выбрать любое число. Начиная со следующего раунда, каждое выбранное число должно быть смежным с любым ранее выбранным числом.
- Мы выбрали клетку \((2, 4)\), в которой находится число \(15\), и которая является соседней с \((3, 4)\).
- Интерактор выбрал клетку \((4, 4)\), в которой находится число \(14\), и которая является смежной с \((3, 4)\).
- Мы выбрали клетку \((4, 3)\), в которой находится число \(1\), и которая является смежной с \((4, 4)\).
- \(\ldots\)
- Это продолжается до тех пор, пока не будут выбраны все числа.
В итоге вы выбрали такие числа: \([15, 1, 16, 5, 4, 2, 11, 13]\), а соперник выбрал \([8, 14, 7, 9, 10, 3, 6, 12]\). Сумма выбранных нами чисел составляет \(67\), что меньше суммы чисел, выбранных соперником: \(69\). Таким образом, мы выиграли эту игру.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
4 4
3 4
4 4
4 2
4 1
1 4
1 2
2 2
2 1
|
2 3 4 10
12 6 11 15
5 13 16 8
9 7 1 14
2 4
4 3
3 3
3 1
1 3
1 1
2 3
3 2
|