#501. 「LibreOJ β Round」ZQC 的树列

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: 匿名

题目描述

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

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

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

给出一个序列 A A 的特征值 k k 1k1018 1 \leq k \leq 10 ^ {18} ),要求构造一个这样的序列 A A 1A5000 1 \leq |A| \leq 5000 0Ai2311 0 \leq A_i \leq 2 ^ {31} - 1 )。

输入格式

一行一个数 k k

输出格式

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

样例

样例输入 1

3

样例输出 1

2
1 1

样例输入 2

233

样例输出 2

qnq