Есть кусок сыра в виде прямоугольника размера NxM.
Маленький мышонок хочет съесть весь кусок сыра. Начав в произвольной клетке, он, поедая очередной кусочек (1х1), переходит в соседний (только если он его еще не съел). Помогите маленькому мышонку составить маршрут по прямоугольнику, чтобы он съел весь сыр.
Входные данные
В строке записаны числа N, M. (1<=N,M<=30)
Выходные данные.
Вывести маршрут мышонка в виде последовательности координат кусочков, которые он съедает.
Кусочки сыра имеют координаты от 1 до N по оси X, от 1 до M по оси Y.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
2 2 |
1 1
2 1
2 2
1 2
|