Проснувшись утром, Толик понял, что ему в голову пришла отличная задача, которая в самый раз подошла бы на Codeforces! Однако, так как в то время еще не было проекта "Обсуждаем задачи", он решил для начала протестировать задачу на своем дяде.

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

В этой задаче вам дано клетчатое поле $$$n \cdot m$$$, состоящее из $$$n$$$ строк и $$$m$$$ столбцов, где клетка имеет координаты $$$(x, y)$$$, если она стоит в $$$x$$$-й строке и $$$y$$$-м столбце, если считать, что нумерация идет с единицы ($$$1 \leq x \leq n, 1 \leq y \leq m$$$). Изначально вы стоите в клетке $$$(1, 1)$$$. На каждом ходу вы можете прыгнуть из клетки $$$(x, y)$$$, где вы сейчас стоите, на любой вектор $$$(dx, dy)$$$, таким образом, оказавшись в клетке $$$(x+dx, y+dy)$$$. Разумеется, нельзя выпрыгивать за пределы поля, однако есть еще одно важное условие — вы не можете прыгать на один вектор два раза. Требуется же вам обойти всё поле, посетив каждую клетку ровно один раз (начальная клетка считается уже посещённой).

Так как дядя Толика очень занятой человек, помогите ему решить эту задачу!