P15855 [蓝桥杯第二届国际赛] 汉诺塔问题

汉诺塔问题是一个经典的数学问题。 给定三根柱子 A、B、C，柱子 A 上按大小顺序放着 $n$ 个大小不同的盘子，最下面的盘子最大，最上面的盘子最小。现在要将所有盘子从柱子 A 移动到柱子 C 中，问最少要移动多少次。 答案是最少 $2^n-1$ 次。而且要以最少的次数完成移动，只存在一种方案。 比如，当 $n=3$ 时，总共要移动 $7$ 步： 第 $1$ 步：最小的盘子中 A 移到 C，记为 A->C； 第 $2$ 步：第 $2$ 小的盘子从 A 移到 B，记为 A->B； 第 $3$ 步：最小的盘子中 C 移到 B，记为 C->B； 第 $4$ 步：第 $3$ 小的盘子从 A 移到 C，记为 A->C； 第 $5$ 步：最小的盘子中 B 移到 A，记为 B->A； 第 $6$ 步：第 $2$ 小的盘子从 B 移到 C，记为 B->C； 第 $7$ 步：最小的盘子中 A 移到 C，记为 A->C。 请问，在第 $x$ 步到第 $y$ 步之间，有多少次 A->B，多少次 A->C，多少次 B->A，多少次 B->C，多少次 C->A，多少次 C->B？

输入的第一行包含一个整数 $n$。 第二行包含两个整数 $x, y$，用一个空格分隔。

输出六行，每行一个整数。分别表示以上六个问题的答案。

### 【数据规模与约定】 对于 $30\%$ 的评测用例，$1 \le n \le 10$，$1 \le x \le y \le 2^n-1$。 对于 $60\%$ 的评测用例，$1 \le n \le 30$，$1 \le x \le y \le 2^n-1$。 对于所有评测用例，$1 \le n \le 100$，$1 \le x \le y \le 2^n-1$，$y \le 10^{18}$。