H - Percepts of AtCoder 2 解説 /

実行時間制限: 3 sec / メモリ制限: 976 MB

配点：1500 点

問題文

E869120 は square1001 に、今年から Q 年間誕生日に数列をプレゼントすることにしました。
square1001 は、「プレゼントする数列の長さが短い方がよりコンパクトで良い」と言ったので、プレゼントする数列は出来るだけ短くしたいです。また、古から伝わる AtCoder 社の教えに基づいて、プレゼントする数列を決める必要があります。

AtCoder 社の教えとは、以下のようなものです。

  • 数列の要素は全て 異なる。
  • プレゼントする数列に部分列として出現する数列のうち、単調増加列であるようなものの種類数はちょうど、聖なる数 K 個である。

ここで、数列 A = (A_1, A_2, ..., A_N) の「部分列」とは、A から 0 個以上 N 個以下の値を消して、残った値の順序を変えずにできる数列のことです。
また、数列 A = (A_1, A_2, ..., A_N) が「単調増加列」である条件は、A_1 < A_2 < ... < A_N であることです。

例えば、A = (3, 4, 1, 2) の時、部分列として出現する「単調増加列」は (), (1), (2), (3), (4), (1, 2), (3, 4) の 7 個です。

AtCoder 社では、毎年「聖なる数」が変わります。具体的には、i 年目の聖なる数は K_i です。
E869120 君のために、i 年目にプレゼントするべき数列を求めてください。

入力

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

Q
K_1
K_2
K_3
...
K_Q

出力

以下のように Q 行に渡って出力してください。

(1 年目の数列の情報)
(2 年目の数列の情報)
(3 年目の数列の情報)
...
(Q 年目の数列の情報)

ただし、数列の情報は以下のように出力してください。 

N A_1 A_2 A_3 ... A_N

出力する数列は、以下の条件を満たす必要があります。

  • 0 \leq N \leq 128
  • 0 \leq A_i \leq 999
  • A_i \neq A_j (i \neq j)

制約

  • Q は 1 以上 1 \ 000 以下の整数
  • K_i は 1 以上 5 \ 000 \ 000 \ 000 \ 000 \ 000 \ 000 \ (= 5 \times 10^{18}) 以下の整数

小課題・得点

  1. (30 点)：K_i \leq 100 を満たす。
  2. (70 点)：K_i \leq 1 \ 500 を満たす。
  3. (1400 点) : 追加の制約はない。

ただし、小課題 3 について、以下のように得点が決定します。
ここでは、Q 年間における N の最大値を L とします。また、全てのテストケースにおける L の最大値を L' とします。

  • 120 \leq L' \leq 128 のとき、この小課題の得点は 125 点
  • 100 \leq L' \leq 119 のとき、この小課題の得点は 1400 \times 5^{-(L' - 99) / 20} 点
  • 0 \leq L' \leq 99 のとき、この小課題の得点は 1400 点

入力例 1

2
5
10

出力例 1

3 2 3 1
6 8 6 9 1 2 0

1 年目のプレゼントとして渡す数列は、(2, 3, 1) です。
この数列には、増加部分列が 5 個あります。(), (1), (2), (3), (2, 3) です。

入力例 2

3
20
100
869120

出力例 2

9 9 7 3 6 5 8 4 1 2
10 0 5 9 3 6 1 4 2 7 8
72 47 45 28 9 41 50 33 61 27 15 38 54 52 22 57 7 30 12 46 21 19 8 71 20 23 6 18 26 17 39 4 53 44 3 31 68 29 42 62 37 69 67 40 65 2 55 36 35 11 49 24 25 43 48 0 1 16 10 70 66 64 32 5 51 60 63 58 56 59 13 14 34

Max Score：1500 points

Problem Statement

E869120 the Coder decided to give a sequence to square1001 as a birthday gift each year, for next Q years.
Since square1001 said that "It is better if the length of sequence is shorter", the length of the sequence should be as short as possible.
Moreover, there is "AtCoder's Percepts" which has been told from ancient times, so he also decided to determine the sequence based on this percepts.

The contents of "AtCoder percepts" is as follows:

  • The elements in sequence should be distinct.
  • The sequence which is about to give, should have exactly K increasing subsequence. (K is "holy number")
  • Subsequence of A = (A_1, A_2, ..., A_N) is the sequence which can make by deleting some (possibly zero or all) elements without changing the order of remaining elements.
  • Note: Also empty sequence is included as a increasing subsequence. In addition, even if the places which has deleted is different, when the resulting subsequence is same, it is regarded as the same subsequence.
  • For example, if A = (3, 4, 1, 2), there are 7 increasing subsequences: (), (1), (2), (3), (4), (1, 2), (3, 4).

In AtCoder, "holy number" will change every year. In i-th year, holy number is K_i.
Please find a sequence which E869120 the Coder should give as a present in each year.

Input

Input is given from Standard Input in the following format: 

Q
K_1
K_2
K_3
...
K_Q

Output

Print Q lines as follows: 

(Information of sequence in 1-st year)
(Information of sequence in 2-nd year)
(Information of sequence in 3-rd year)
...
(Information of sequence in Q-th year)

You should output the information of sequence as follows: 

N A_1 A_2 A_3 ... A_N

Note N is the length of A.
The sequence should satisfy these conditions:

  • 0 \leq N \leq 128
  • 0 \leq A_i \leq 999
  • A_i \neq A_j (i \neq j)

Constraints

  • Q is an integer between 1 and 1 \ 000 (inclusive)
  • K_i is an integer between 1 and 5 \ 000 \ 000 \ 000 \ 000 \ 000 \ 000 \ (= 5 \times 10^{18}) (inclusive)

Subtasks / Scoring

  1. (30 points)：K_i \leq 100
  2. (70 points)：K_i \leq 1 \ 500
  3. (1400 points) : There are no additional constraints.

In subtask 3, the score will be determined as follows.
Let L be the maximum value of N in this testcase, and let L' be the maximum value of L in all testcases in subtask 3.

  • 120 \leq L' \leq 128 : 125 points in subtask 3
  • 100 \leq L' \leq 119 : 1400 \times 5^{-(L' - 99) / 20} points in subtask 3
  • 0 \leq L' \leq 99 : 1400 points in subtask 3

Sample Input 1

2
5
10

Sample Output 1

3 2 3 1
6 8 6 9 1 2 0

The sequence that E869120 gives in 1st year is (2, 3, 1).
There are 5 increasing subsequence: (), (1), (2), (3), (2, 3).

Sample Input 2

3
20
100
869120

Sample Output 2

9 9 7 3 6 5 8 4 1 2
10 0 5 9 3 6 1 4 2 7 8
72 47 45 28 9 41 50 33 61 27 15 38 54 52 22 57 7 30 12 46 21 19 8 71 20 23 6 18 26 17 39 4 53 44 3 31 68 29 42 62 37 69 67 40 65 2 55 36 35 11 49 24 25 43 48 0 1 16 10 70 66 64 32 5 51 60 63 58 56 59 13 14 34