У вас есть полное бинарное дерево с бесконечным количеством уровней.
В каждой вершине записано значение. Если в вершине записано значение x, то в ее левом потомке записано значение 2·x, а в правом потомке — значение 2·x + 1.
Значение, записанное в корне, равно 1.
Вам нужно обработать Q запросов.
Всего есть 3 типа запросов:
- Циклически сдвинуть на K значения, записанные во всех вершинах, которые находятся на одном уровне с вершиной, в которой записано значение X. (Вершины и значения, записанные в вершинах, на других уровнях остаются без изменений).
- Циклически сдвинуть на K вершины, которые находятся на одном уровне с вершиной, в которой записано значение X. (Поддеревья сдвигаемых вершин двигаются вместе с ними).
- Вывести значения, записанные в каждой из вершин, которые встречаются на простом пути из вершины, в которой записано значение X, до корня.
Положительное K означает циклический сдвиг вправо, а отрицательное K означает циклический сдвиг влево.
Гарантируется, что среди запросов есть хотя бы один, который имеет тип 3.
Выходные данные
Для каждого запроса типа 3 выведите в порядке убывания значения, записанные во всех вершинах, встречающихся на пути.
Примечание
На картинках ниже изображены первые 4 уровня дерева для первого примера:
Изначальное дерево:
Дерево после запроса 1 2 1:
Дерево после запроса 2 4 -1:
