長さ $n$ の数列 $a = (a_1, \dots, a_n)$ に対し、$f(a)$ を次の条件をすべて満たす整数 $(i, j, k)$ の組の個数と定義します。この定義はE問題と同じです。

• $1 \le i < j < k \le n$
• $a_i \ne a_j$
• $a_i \ne a_k$
• $a_j = a_k$

正整数 $M$ が与えられます。次の条件をすべて満たす長さ $N$ の数列 $A$ を $1$ つ答えてください。

• $3 \le N \le 2 \times 10^5$
• すべての $1 \le i \le N$ について、$1 \le A_i \le N$
• $f(A) = M$

なお、本問題の制約下で、条件をすべて満たす $A$ が $1$ つ以上存在することが証明できます。また、条件をすべて満たす $A$ が複数存在する場合、どれを答えても構いません。

この問題では、Easy の部分点の獲得方法が他の問題と異なります。

Hard (100点)

• $0 \le M \le {10}^{14}$
• $M$ は整数

Easy (100点)

• Hard の制約に以下の制約を追加
• $M \in \lbrace 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 \rbrace$
  • $M$ の値に応じて、次の点数が割り振られている。それぞれのケースに正解すると、割り振られた点数を獲得することができる。
    • $M = 2, 3$ : $2$ 点
    • $M = 5, 8$ : $6$ 点
    • $M = 13, 21$ : $10$ 点
    • $M = 34, 55$ : $14$ 点
    • $M = 89, 144$ : $18$ 点
  • 例えば、$M = 2, 3, 8, 34$ のケースに正解した場合、$2 + 2 + 6 + 14 = 24$ 点を獲得できる。

入力は以下の形式で標準入力から与えられます。

答えを次の形式で出力してください。