题目描述

卢卡斯认为，他六岁的儿子已经可以学习一些基础算法了。作为起点，他选择了一种非常优美的技术：递归。为了展示递归，他挑选了一个著名的递归游戏——汉诺塔。

汉诺塔是一种数学游戏，由三根杆子和若干不同直径的圆盘组成，这些圆盘可以滑动到任意一根杆子上。游戏开始时，圆盘按大小顺序堆叠在第一根杆子上，最小的圆盘在最上面，从而形成一个近似锥形的形状。游戏的目标是将整个堆叠转移到最后一根杆子上，同时遵守以下规则：

• 每次只能移动一个圆盘。
• 每次移动是将一个堆叠顶部的圆盘拿起，放在另一个堆叠的顶部或空杆子上。
• 不能将一个圆盘放在比它小的圆盘上面。

卢卡斯知道，解决汉诺塔游戏所需的最小移动次数是 $2^{n}-1$，其中 $n$ 是圆盘的数量。更重要的是，最优移动是唯一的，这意味着 $n$ 和已经完成的移动次数唯一地表示了游戏的当前状态，前提是圆盘总是按最优方式移动。

卢卡斯正在一步步向儿子展示如何解决这个游戏。他已经完成了前 $k$ 次最优移动。由于完成游戏还需要一段时间，他中途休息了一下，去拿了些零食。不幸的是，当他回来时，他发现自己顽皮的小儿子做了一个大「移动」：知道目标是将所有圆盘从第一根杆子转移到最后一根杆子，他的儿子直接在一次移动中「将第一根杆子上的所有圆盘转移到最后一根杆子上」（没有改变它们的相对顺序），参见图 K.1。

卢卡斯认为这仍然是一个教学机会。他决定继续使用“合法”的移动来解决游戏。然而，他想知道当前完成游戏所需的最小移动次数。由于他还要忙于处理儿子的事务，他需要你的帮助！

请注意，即使给定的状态是无效的，「合法」移动仍然是明确定义的。换句话说，每次只能移动一个顶部的圆盘，并且不能将其放在比它小的圆盘上。特别是，将大小为 $a$ 的圆盘放在包含大小为 $b$ $(b < a)$ 圆盘的杆子上是合法的，如果该杆子顶部的圆盘大小为 $c$ $(a < c)$。

输入格式

第一行包含一个整数 $n$ $(1 \leq n \leq 200\,000)$，表示游戏中的圆盘数量。

第二行包含一个整数 $k$ $(0 \leq k \leq 2^{n}-1)$，表示卢卡斯在大「移动」之前完成的最优移动次数。注意，$k$ 以二进制形式给出。

输出格式

输出一个以二进制表示的整数，表示完成游戏所需的最小移动次数。

3
0

0

3
10

110

5
11011

11