Problem Description

BISCO, the dog owned by Takahashi, has worked for 29 years at Disco Corporation and has finally reached retirement. Due to his significant contributions to the company, he was presented with a "Golden Square Chip" by the president, WISCO.

This chip contains a secret integer $ N $ as data, and BISCO knows that $ N $ is an integer between $ 1 $ and $ 10^{12} $ inclusive. However, only the president can view the actual value of this integer $ N $.

Since BISCO was eager to know the secret integer, President WISCO provided the following values as hints:

• $ a_2, a_3, a_4, ..., a_{30} $ of 29 values.
• Here, $ a_i $ is the sum of the digits when the integer $ N $ is represented in base $ i $.

For example, when $ N = 1123 $, representing $ N $ in base 4 results in 101203, so $ a_4 = 1 + 0 + 1 + 2 + 0 + 3 = 7 $.

For BISCO's sake, guess the secret integer $ N $ based on the hints. If there are multiple possible numbers for the secret integer, output any one of them. If no such number exists, output invalid.

Input Format

The input is given from the standard input in the following format:

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

Output Format

Output one possible number for the secret integer $N (\leq 10^{12})$. If no such number exists, output invalid.

Sample Input and Output

Sample Input #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

Sample Output #1

25

Sample Input #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

Sample Output #2

invalid

Sample Input #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

Sample Output #3

201811232111

Sample Input #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

Sample Output #4

invalid

Notes/Hints

Constraints

• $ a_2, a_3, a_4, ..., a_{30} $ are all integers between $ 1 $ and $ 500 $ inclusive.

Sample Explanation 1

$ N = 25 $ is a possible number for the secret integer. - When $ 25 $ is represented in base 2, it is 11001, and the sum of the digits is $ 3 $, which equals $ a_2 $. - When $ 25 $ is represented in base 3, it is 221, and the sum of the digits is $ 5 $, which equals $ a_3 $. This property is also satisfied for $ a_4 $ to $ a_{30} $.

Sample Explanation 2

Focusing on $ a_2 = 500 $. The smallest positive integer whose sum of digits when represented in base 2 is $ 500 $ is $ 2^{500} - 1 $, which significantly exceeds the upper limit of the secret integer $ N $, which is $ 10^{12} $. Therefore, no possible number exists for the secret integer.

Sample Explanation 3

$ 201811232111 $ is a possible number for the secret integer.

Sample Explanation 4

Note that the secret integer must be $ 10^{12} $ or less. (Without this condition, $ 1000000000001 $ would be a possible number for the secret integer.)

见题面 Input 部分

见题面 Output 部分