You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

在一棵高度为 $n$ 的完美二叉树中，给定两个整数 $a,b$ ，求标号为 $a,b$ 的点的最近公共祖先。

输入格式

输入由一行构成，包含三个正整数，分别为 $n, a, b$ ，其中：

• $n$ 为完美二叉树的高度，$1 \le n \le 30$ 。
• $a,b$ 为树中两个节点的标号，满足 $1 \le a, b \le 2^n - 1$ 。

输出格式

输出一个整数，即节点 $a$ 和节点 $b$ 的最近公共祖先的标号。

输入输出样例 #1

输入 #1

4 4 10

输出 #1

2

说明/提示

关于完美二叉树的定义、标号规则、最近公共祖先的定义等详见纸质题面。