分数: 100 点
问题陈述
给你一个整数 N。考虑一个无穷大 N-二叉树如下所示:
图:无限 N- 案例的二叉树 N = 3
如图所示,每个顶点都用唯一的正整数进行索引,并且对于每个正整数都有一个用它索引的顶点。树的根有索引 1。对于其余的顶点,上行中的顶点具有比下行中的顶点小的索引。在同一行的顶点中,越靠左的顶点索引越小。
关于这棵树,处理 Q 查询。的 i第查询如下:
- 查找 Vertex 的最低共同祖先(见注释)的索引 v_i 和 w_i.
注释
- 在有根树中, 顶点的 最低共同祖先 (LCA) v 和 w 是距离根最远的顶点,它是两个顶点的祖先 v 和 w。这里,顶点被认为是其自身的祖先。例如,在Problem Statement所示的树中,Vertex的LCA 5 和 7 是顶点 2,Vertex 的 LCA 8 和 11 是顶点 1,以及 Vertex 的 LCA 3 和 9 是顶点 3.
约束
- 1 ≤ N ≤ 10^9
- 1 ≤ Q ≤ 10^5
- 1 ≤ v_i < w_i ≤ 10^9
输入
输入由标准输入按以下格式给出:
N Q v_1 w_1 : v_Q w_Q
输出
打印 Q 行。的 i第行 (1 ≤ i ≤ Q) 必须包含 Vertex 的最低共同祖先的索引 v_i 和 w_i.
样本输入 1
3 3 5 7 8 11 3 9
示例输出 1
2 1 3
本例中的查询对应于注释中显示的示例。
示例输入 2
100000 2 1 2 3 4
示例输出 2
1 1