Кривая дракона над Таласом
Над Таласской долиной запускают воздушного змея-дракона, а его хвост оставляет на клетчатой карте ломаную. Ломаная начинается в точке (0, 0) и состоит из отрезков длины 1, первый отрезок идёт на восток — в точку (1, 0).
После n-го отрезка (n ≥ 1) змей поворачивает на 90°. Направление поворота определяется так: запишем n = 2^t · (2j + 1), где j и t — целые неотрицательные числа. Если j чётное, змей поворачивает налево (против часовой стрелки), если нечётное — направо.
Получается знаменитая кривая дракона (её также получают, если много раз сложить полоску бумаги пополам и развернуть её под прямыми углами).
Обозначим через P(N) точку, в которой окажется змей после N отрезков, P(0) = (0, 0). Ответьте на q запросов: по числу N найдите P(N).
Входные данные
В первой строке — число q (1 ≤ q ≤ 10⁵). В каждой из следующих q строк — одно целое число N (0 ≤ N ≤ 10¹⁸).
Выходные данные
Для каждого запроса выведите два целых числа — координаты x и y точки P(N). Ось x направлена на восток, ось y — на север.
Пример 1
Вход:
6
0
1
2
5
6
8
Выход:
0 0
1 0
1 1
-1 2
-1 1
-2 2
Пояснение
Первые точки ломаной: (0, 0), (1, 0), (1, 1), (0, 1), (0, 2), (−1, 2), (−1, 1), … После первого отрезка (n = 1, j = 0) змей повернул налево, после второго (n = 2, снова j = 0) — тоже налево, после третьего (n = 3, j = 1) — направо.
Система оценивания
Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 30 % тестов N ≤ 10⁶.
Комментарии