Nami 即将得到一个包含 $n$ 个正整数的序列 $S = S_1, S_2, \dots, S_n$，她想要将其划分为两个子序列。

起初，Nami 有两个空序列 $S_A$ 和 $S_B$。她会按顺序考虑 $S$ 中的每个整数，并将其追加到 $S_A$ 或 $S_B$ 中。Nami 将最终得到的序列 $S_A, S_B$ 称为 $S$ 的一种划分。注意，$S_A$ 和 $S_B$ 是不同的，且子序列可以为空，因此将 $S$ 划分为 $S_A$ 和 $S_B$ 的方式共有 $2^n$ 种，这意味着 $S$ 有 $2^n$ 种可能的划分。

对于一种划分，假设 $S_A$ 中有 $n_A$ 个整数，$S_B$ 中有 $n_B$ 个整数，当且仅当满足以下条件时，Nami 称其为“伟大划分”： $S_{A,1} \le S_{A,2} \le \dots \le S_{A,n_A}$ $S_{B,1} \ge S_{B,2} \ge \dots \ge S_{B,n_B}$

Nami 将 $S$ 的“伟大度”定义为 $S$ 的不同伟大划分的数量。现在 Nami 给你一个魔术数字 $k$，你的任务是为她找到一个伟大度等于 $k$ 的序列 $S$。

注意，$S$ 的长度不应超过 $365$，$S$ 中的正整数不应超过 $10^8$。

如果有多个可能的序列，你可以输出其中任意一个。如果不存在伟大度等于 $k$ 的序列，输出 $-1$。

输入格式

输入包含一个整数 $k$ ($0 \le k \le 10^8$) —— Nami 给出的魔术数字。

输出格式

如果不存在伟大度等于 $k$ 的序列，输出 $-1$。

否则，第一行输出序列 $S$ 的长度 $n$ ($1 \le n \le 365$)。 第二行输出 $n$ 个正整数 $S_1, S_2, \dots, S_n$ ($1 \le S_i \le 10^8$) —— Nami 所需的序列。

样例

样例输入 1

6

样例输出 1

6
1 1 4 5 1 4

样例输入 2

1

样例输出 2

1
1

说明

对于序列 $S = 1, 1, 4, 5, 1, 4$，可以证明其唯一的伟大划分是： * $S_A = 1, 1, 4, 4, S_B = 5, 1$

对于序列 $S = 1$，可以证明 $S$ 的所有划分都是伟大的： $S_A = 1, S_B$ 为空 $S_A$ 为空, $S_B = 1$