题目描述

ZQC 和妹子来到了一片小树林，看到一列列参差不齐的树，ZQC 想到了一种评价每一列树的美观程度的方法 —— 将相邻两棵树高度差的总和作为一列树的美观度。即，设一列树的高度组成的序列为 $ A $，则其美观度为 $ f(A) = \sum\limits_{i = 1} ^ {|A| - 1} |Ai - A{i + 1}| $。

ZQC 想，每一列树都有一些特征，于是他钦定了一列树的特征值 —— 设 $ S $ 为 $ A $ 的美观度最大的子序列，若 $ A $ 有 $ k $ 个子序列 $ T_i $ 的美观度与 $ S $ 相同（即 $ f(T_i) = f(S) $），则称 $ A $ 的特征值为 $ k $。注意，子序列不能为空。

ZQC 的妹子非常喜欢 $ k $ 这个特征值，她希望 ZQC 能给她种一列特征值为 $ k $ 的树。按照套路，这么简单的问题 ZQC 当然不会亲自出马，所以他钦定你来解决这个问题。

给出一个序列 $ A $ 的特征值 $ k $（$ 1 \leq k \leq 10 ^ {18} $），要求构造一个这样的序列 $ A $（$ 1 \leq |A| \leq 5000 $，$ 0 \leq A_i \leq 2 ^ {31} - 1 $）。

输入格式

一行一个数 $ k $。

输出格式

如果有解，输出两行。第一行一个正整数 $ n $。第二行 $ n $ 个正整数表示构造的序列 $ A $。
如果无解，输出一行 qnq。

样例 1

input

3

output

2
1 1

样例 2

input

233

output

qnq