您有一个具有无限级别的完整二叉树。
每个节点都有一个初始值。如果节点的值为 x,则其左子节点的值为 2·x,右子节点的值为 2·x + 1。
根的值为 1。
您需要回答Q问题。
有 3 种类型的查询:
1.将与值为X的节点同级的所有节点的值循环平移K个单位。 (任何其他级别的值/节点不受影响)。
2.将与值为X的节点同级的节点循环移位K个单位。 (这些节点的子树将随之移动)。
3. 打印从值为 X 的节点到根的简单路径上遇到的每个节点的值。
正 K 表示右循环移位,负 K 表示左循环移位。
保证至少存在一个类型 3 查询。
输入
第一行包含一个整数 Q (1 ≤ Q ≤ 105)。
然后是 Q 查询,每行一个:
- 类型 1 和 2 的查询具有以下格式:T X K (1 ≤ T ≤ 2; 1 ≤ X ≤ 1018; 0 ≤ |K| ≤ 1018),其中 T 是查询的类型。
- 类型 3 的查询具有以下格式:3 X (1 ≤ X ≤ 1018)。
输出
对于类型 3 的每个查询,按降序打印遇到的所有节点的值。
示例
输入 #1
5 3 12 1 2 1 3 12 2 4 -1 3 8
输出 #1
12 6 3 1 12 6 2 1 8 4 2 1
输入 #2
5 3 14 1 5 -3 3 14 1 3 1 3 14
输出 #2
14 7 3 1 14 6 3 1 14 6 2 1
注意
以下是第一个测试用例中树的前 4 层的图像:
原文:
查询1 2 1后:
查询2 4 -1后: