Задача I. Шахматный король

Автор:А. Кленин, Е. Шавлюгин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Дана шахматная доска размером N × M клеток. Клетки на ней обозначаются парами координат — номерами вертикали и горизонтали.

В клетке (1, 1) расположен шахматный король. Требуется обойти королём доску, побывав в каждой клетке ровно один раз, и вернувшись в исходную позицию.

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

Формат входного файла

Входной файл содержит числа N M.

Формат выходного файла

Выходной файл должен содержать N × M пар чисел v h — координаты клеток, через которые проходит путь короля (1 ≤ v ≤ N, 1 ≤ h ≤ M). Первая клетка в пути должна иметь координаты (1, 1), а последняя — (1, 2), (2, 1) или (2, 2). Если имеется несколько решений, вывести любое из них.

Ограничения

2 ≤ N, M ≤ 100.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
4 2
1 1  2 1  3 1  4 1  4 2  3 2  2 2  1 2

0.036s 0.008s 15