I. Игра на сетке
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это интерактивная задача.

Вам дана сетка из $$$n$$$ строк и $$$m$$$ столбцов. Вам нужно заполнить каждую ячейку уникальным целым числом от $$$1$$$ до $$$n \cdot m$$$.

После заполнения сетки вы сыграете с интерактором в игру на этой сетке. Игроки по очереди выбирают из сетки ранее не выбранные ячейки, причем интерактор ходит первым.

В первый ход интерактор может выбрать любую ячейку из сетки. После этого любая выбранная клетка должна быть соседней по стороне хотя бы с одной ранее выбранной клеткой. Игра продолжается до тех пор, пока не будут выбраны все клетки.

Ваша цель состоит в том, чтобы сумма чисел в выбранных вами клетках была строго меньше суммы чисел в клетках, выбранных соперником.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Единственная строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$4 \le n, m \le 10$$$) — количество строк и столбцов в сетке.

Протокол взаимодействия

Сначала выведите $$$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;
  • смотрите документацию для других языков.

Взломы в этой задаче отключены.

Пример
Входные данные
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
Примечание

Обратите внимание, что это пример игры и не обязательно представляет собой оптимальную стратегию для обоих игроков.

Сначала мы заполнили сетку $$$4 \times 4$$$ различными целыми числами от $$$1$$$ до $$$16$$$ следующим образом:

$$$2$$$$$$3$$$$$$4$$$$$$10$$$
$$$12$$$$$$6$$$$$$11$$$$$$15$$$
$$$5$$$$$$13$$$$$$16$$$$$$8$$$
$$$9$$$$$$7$$$$$$1$$$$$$14$$$

Далее началась игра.

  1. Сначала соперник выбирает клетку $$$(3, 4)$$$, в которой находится число $$$8$$$. Во время первого раунда интерактор может выбрать любое число. Начиная со следующего раунда, каждое выбранное число должно быть смежным с любым ранее выбранным числом.
  2. Мы выбрали клетку $$$(2, 4)$$$, в которой находится число $$$15$$$, и которая является соседней с $$$(3, 4)$$$.
  3. Интерактор выбрал клетку $$$(4, 4)$$$, в которой находится число $$$14$$$, и которая является смежной с $$$(3, 4)$$$.
  4. Мы выбрали клетку $$$(4, 3)$$$, в которой находится число $$$1$$$, и которая является смежной с $$$(4, 4)$$$.
  5. $$$\ldots$$$
  6. Это продолжается до тех пор, пока не будут выбраны все числа.

В итоге вы выбрали такие числа: $$$[15, 1, 16, 5, 4, 2, 11, 13]$$$, а соперник выбрал $$$[8, 14, 7, 9, 10, 3, 6, 12]$$$. Сумма выбранных нами чисел составляет $$$67$$$, что меньше суммы чисел, выбранных соперником: $$$69$$$. Таким образом, мы выиграли эту игру.