你即将推出一款每个人都想玩的新网络游戏。然而，你的服务器还没有准备好处理这么多玩家。更准确地说，你的服务器可以处理 $n$ 名玩家。当然，你希望玩家越多越好，因为这能为你带来尽可能多的收入。换句话说，你的目标是恰好拥有 $n$ 名玩家。

公开承认服务器的现状对你的公司来说意味着糟糕的公关。因此，你决定以另一种方式限制玩家数量：通过限制他们对用户名的选择，使得恰好存在 $n$ 个合法的用户名。

合法的用户名必须满足以下条件： 长度恰好为 $k$。 仅由字母 A 和 B 组成。 * 不包含禁用的子串列表 $s_1, s_2, \dots, s_m$ 中的任何字符串作为子串。

你需要选择 $k$、$m$ 以及字符串 $s_1, s_2, \dots, s_m$，使得恰好存在 $n$ 个合法的用户名。请参阅输出格式以了解你所选数值的限制。

输入格式

输入文件的唯一一行包含一个整数 $n$，$1 \le n \le 10^9$。

输出格式

在输出文件的第一行，打印两个整数 $k$ 和 $m$：用户名的长度以及禁用子串的数量。在接下来的 $m$ 行中，打印这些禁用子串。

必须满足以下条件： $1 \le k \le 60$。 $0 \le m \le 100$。 每个禁用子串 $s_i$ 的长度在 $1$ 到 $k$ 之间，且仅由字母 A 和 B 组成。 对于你输出的数值，恰好存在 $n$ 个合法的用户名。

保证解一定存在。你可以输出任何合法的解。禁用子串可以相同，也可以互为子串。

样例

样例输入 1

5

样例输出 1

3 1
BB

样例输入 2

6

样例输出 2

3 2
ABB
BBB

样例输入 3

8

样例输出 3

3 0