E. Раскраска сетки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана сетка размером $$$n\times m$$$, где каждая ячейка изначально белая. Вам нужно раскрасить все ячейки по одной. После того как вы раскрасите ячейку, все раскрашенные ячейки, находящиеся дальше всего от неё, получают штраф. Найдите порядок раскраски, при котором ни одна ячейка не получит более $$$3$$$ штрафов.

Обратите внимание, что $$$n$$$ и $$$m$$$ оба нечетные.

Используемая метрика расстояния — это Расстояние Чебышёва, а ничьи между ячейками мы решаем с помощью манхэттенского расстояния. Формально, ячейка $$$(x_2, y_2)$$$ находится дальше от ячейки $$$(x_1, y_1)$$$, чем $$$(x_3, y_3)$$$, если выполняется одно из следующих условий:

  • $$$\max\big(\lvert x_1 - x_2 \rvert, \lvert y_1 - y_2 \rvert\big) \gt \max\big(\lvert x_1 - x_3 \rvert, \lvert y_1 - y_3 \rvert\big)$$$
  • $$$\max\big(\lvert x_1 - x_2 \rvert, \lvert y_1 - y_2 \rvert\big)=\max\big(\lvert x_1 - x_3 \rvert, \lvert y_1 - y_3 \rvert\big)$$$ и $$$\lvert x_1 - x_2 \rvert + \lvert y_1 - y_2 \rvert \gt \lvert x_1 - x_3 \rvert + \lvert y_1 - y_3 \rvert$$$

Можно доказать, что всегда существует хотя бы одно решение.

Пример, показывающий изменения штрафов после раскраски центра сетки $$$5 \times 5$$$. Числа указывают на штраф ячеек.
Входные данные

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

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

Гарантируется, что сумма $$$n \cdot m$$$ по всем наборам входных данных не превосходит $$$5000$$$.

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

Для каждого набора входных данных выведите $$$n \cdot m$$$ строк, где $$$i$$$-я строка должна содержать координаты $$$i$$$-й ячейки в вашем порядке раскраски. Если существует несколько решений, выведите любое из них.

Пустые строки в примере вывода предназначены только для повышения читаемости. Вы не обязаны их выводить.

Пример
Входные данные
3
3 3
1 1
1 5
Выходные данные
2 1
2 3
2 2
1 1
3 2
3 3
3 1
1 3
1 2

1 1

1 2
1 4
1 5
1 1
1 3
Примечание

В первом наборе входных данных сетку можно раскрасить следующим образом:

Числа указывают на штраф ячеек.