题目描述

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

3

2
1 1

233

qnq