В космические шахматы играют на бесконечной доске, поэтому клетки нумеруют парой чисел (см. пример и рисунок к нему). Фигуры ходят по обычным правилам. Составьте маршрут шахматного коня из клетки (0; 0) в заданную клетку (x; y).
Напомним, что конь за один ход перемещается на одну клетку по одной оси и на две по другой, то есть, например, из клетки (0; 0) он за один ход может попасть в клетки (1; 2), (2; 1), (-1; 2), (2; -1), (1; -2), (-2; 1), (-1; -2) и (-2; -1).
В качестве ответа Вам нужно вывести любой (не обязательно кратчайший) маршрут с началом в (0; 0) и концом в (x; y), длина которого не больше 10
5 ходов.
Формат входных данных
Программа получает на вход два целых числа x и y, записанных в отдельных строках, - координаты конечной клетки маршрута коня. Клетка (x; y) не совпадает с началом координат. |x| <= 10
5, |y| <= 10
5.
Формат выходных данных
Программа должна вывести последовательность ходов, один ход в отдельной строке. В i-й строке должно быть выведено два числа x
i и y
i через пробел - координаты клетки, в которой окажется конь после i-го хода. Количество ходов не должно превышать 10
5. Последний ход должен вести в заданную клетку
| Ввод |
Вывод |
-2
2 |
-2 1
0 2
-1 0
-2 2 |
Рисунок к примеру
