← 返回题目列表

AtCoder · relay2_b

B. 常青树

中文机器翻译题面 查看原题

分数: 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