Задача: Кривая дракона
Сегодня мальчик Саша на уроке математики узнал про фракталы. Учитель показывал так называемую «кривую дракона». Она представляет собой геометрическую фигуру, которая строится следующим образом: на первом шаге проводится отрезок из начала координатной плоскости в точку (0; 1). Далее на каждом шаге из конца фрактала повторяется уже нарисованная часть фигуры, повернутая на 90 градусов против часовой стрелки (см. рисунок).
После уроков Саша попробовал сам изобразить «кривую дракона», и теперь он хочет знать, в какой точке координатной плоскости он закончил рисовать фрактал, проделав описанные выше N шагов. Требуется написать программу, которая по заданному числу N определяет координаты конца фрактала после выполнения N шагов.
Входные данные
Вводится одно целое число
N (1 <= N <= 30).
Выходные данные
Выведите два числа через пробел - координаты конца фрактала.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
2 |
1 1 |
| 2 |
4 |
2 -2 |
Ваш ответ: