分数: 600 点
问题陈述
对于非负整数 K,我们定义水平分形 K 如下:
- 水平分形 0 是一个只有一个白色方块的网格。
- 当 K > 0,水平分形 K 是 3^K \times 3^K 网格。如果我们把这个网格分成九个 3^{K-1} \times 3^{K-1} 子网格:
- 中央子网格仅由黑色方块组成。
- 其他八个子网格都是水平分形 K-1.
例如,水平分形 2 如下:

在水平分形中 30,让 (r, c) 表示 r从顶部开始的第行和 c左起第 列。
你被给予 Q 整数的四元组 (a_i, b_i, c_i, d_i)。 对于每个四元组,求距离 (a_i, b_i) to (c_i, d_i).
这里距离 (a, b) to (c, d) 是最小整数 n 满足以下条件:
- 存在一系列白色方块 (x_0, y_0), \ldots, (x_n, y_n) 满足以下条件:
- (x_0, y_0) = (a, b)
- (x_n, y_n) = (c, d)
- 对于每个 i (0 \leq i \leq n-1), (x_i, y_i) 和 (x_{i+1}, y_{i+1}) 分享一面。
约束
- 1 \leq Q \leq 10000
- 1 \leq a_i, b_i, c_i, d_i \leq 3^{30}
- (a_i, b_i) \neq (c_i, d_i)
- (a_i, b_i) 和 (c_i, d_i) 是白色方块。
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
Q a_1 \ b_1 \ c_1 \ d_1 : a_Q \ b_Q \ c_Q \ d_Q
输出
打印 Q 行。 的 i第行应包含距 (a_i, b_i) to (c_i, d_i).
示例输入 1
2 4 2 7 4 9 9 1 9
示例输出 1
5 8
