配点: $700$ 点

問題文

高橋君の飼い犬の BISCO は, ディスコ株式会社に 29 年務め, ついに退職の時を迎えた. 彼は会社に大きく貢献したため, 社長の WISCO から「黄金の正方形チップ」をプレゼントされた.

このチップには, 秘密の整数 $N$ がデータとして入っており, BISCO は $N$ が $1$ 以上 $10^{12}$ 以下の整数であることを知っている.
しかし, この整数 $N$ の実際の値は社長しか閲覧することができない.

それでも BISCO が秘密の整数を知りたがったので, 社長の WISCO は, 以下の値をヒントとして与えた.

• $a_2, a_3, a_4, ..., a_{30}$ の $29$ 個の値.
• ただし, $a_i$ は「整数 $N$ を $i$ 進数で表したときの各位の桁の和」である.

例えば, $N = 1123$ のとき, $N$ を $4$ 進数で表すと 101203 となるため, $a_4 = 1 + 0 + 1 + 2 + 0 + 3 = 7$ となる.

BISCO のために, ヒントをもとにして秘密の整数 $N$ を当てなさい.
ただし, 秘密の整数としてあり得る数が複数存在する場合はそのうちのどれを出力してもよく, そのような数が存在しない場合は invalid と出力しなさい.

制約

• $a_2, a_3, a_4, ..., a_{30}$ はすべて $1$ 以上 $500$ 以下の整数

---

入力

入力は, 以下の形式で標準入力から与えられる.

$a_2$ $a_3$ $a_4$ $:$ $a_{30}$

出力

秘密の整数 $N (\\leq 10^{12})$ としてあり得る数を $1$ つ出力せよ. ただし, そのような数が存在しない場合は invalid と出力せよ.

---

入力例 1

3
5
4
1
5
7
4
9
7
5
3
13
12
11
10
9
8
7
6
5
4
3
2
1
25
25
25
25
25

出力例 1

25

$N = 25$ は, 秘密の整数としてあり得る数である.

• $25$ を $2$ 進数で表すと 11001 となり, 各位の桁の和は $3$ で, これは $a_2$ に等しい.
• $25$ を $3$ 進数で表すと 221 となり, 各位の桁の和は $5$ で, これは $a_3$ に等しい.

この性質は, $a_4$ から $a_{30}$ までについても同じように満たされる.

---

入力例 2

500
30
33
36
39
42
45
48
51
54
57
69
63
66
69
72
75
78
81
84
87
90
93
96
99
102
105
108
111

出力例 2

invalid

$a_2 = 500$ に注目する.
$2$ 進数で表したときに各位の桁の和が $500$ となるような最小の正の整数は $2^{500} - 1$ で, これは秘密の整数 $N$ の値の上限である $10^{12}$ を大きく超える.
したがって, 秘密の整数としてありうる数は存在しない.

---

入力例 3

23
27
35
31
36
29
55
63
23
61
49
47
86
69
86
111
63
113
63
71
104
93
95
95
111
125
167
111
111

出力例 3

201811232111

$201811232111$ は, 秘密の整数としてあり得る数である.

---

入力例 4

14
25
20
13
31
41
30
49
2
61
68
65
67
65
56
65
65
83
27
81
107
101
106
41
126
93
83
121
108

出力例 4

invalid

秘密の整数は $10^{12}$ 以下であることに注意せよ. (この条件を除けば, $1000000000001$ が秘密の整数としてあり得る数となる.)