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

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

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

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