問題文

高橋君の飼い犬の 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 以下の整数

入力例 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 が秘密の整数としてあり得る数となる.)