Full Binary Tree Queries

무한히 많은 레벨을 가진 포화 이진 트리가 있다.

각 노드에는 초기값이 있다. 어떤 노드의 값이 x이면, 그 왼쪽 자식의 값은 2·x이고 오른쪽 자식의 값은 2·x + 1이다.

루트의 값은 1이다.

Q개의 쿼리에 답해야 한다.

쿼리는 3가지 유형이 있다.

1. 값이 X인 노드와 같은 레벨에 있는 모든 노드의 값을 K칸 순환 이동한다. (다른 모든 레벨의 값과 노드는 영향을 받지 않는다.)
2. 값이 X인 노드와 같은 레벨에 있는 노드들을 K칸 순환 이동한다. (이 노드들의 서브트리도 함께 이동한다.)
3. 값이 X인 노드에서 루트까지의 단순 경로에서 만나는 모든 노드의 값을 출력한다.

Positive K이면 오른쪽 순환 이동을 의미하고, K가 음수이면 왼쪽 순환 이동을 의미한다.

유형 3의 쿼리가 적어도 하나 존재함이 보장된다.

첫째 줄에 하나의 정수 Q (1 ≤ Q ≤ 105)가 주어진다.

이후 Then Q개의 쿼리가 한 줄에 하나씩 주어진다.

• 유형 1과 2의 쿼리는 다음 형식으로 주어진다: T X K (1 ≤ T ≤ 2; 1 ≤ X ≤ 1018; 0 ≤ |K| ≤ 1018). 여기서 T는 쿼리의 유형이다.
• 유형 3의 쿼리는 다음 형식으로 주어진다: 3 X (1 ≤ X ≤ 1018).

유형 3의 각 쿼리에 대해, 만나는 모든 노드의 값을 내림차순으로 출력한다.

다음은 첫 번째 테스트 케이스에서 트리의 처음 4개 레벨을 나타낸 그림이다.

원래 상태:

쿼리 1 2 1 이후:

쿼리 2 4 -1 이후: