Counting 1's

Problem Statement

Let b_i(x) be the i-th least significant bit of x, i.e. the i-th least significant digit of x in base 2 (i \geq 1). For example, since 6 = (110)_2, b_1(6) = 0, b_2(6) = 1, b_3(6) = 1, b_4(6) = 0, b_5(6) = 0, and so on.

Let A and B be integers that satisfy 1 \leq A \leq B \leq 10^{18}, and k_i be the number of integers x such that A \leq x \leq B and b_i(x) = 1.

Your task is to write a program that determines A and B for a given \{k_i\}.

Input

The input consists of multiple datasets. The number of datasets is no more than 100,000. Each dataset has the following format:

n k_1 k_2 ... k_n

The first line of each dataset contains an integer n (1 \leq n \leq 64). Then n lines follow, each of which contains k_i (0 \leq k_i \leq 2^{63} - 1). For all i > n, k_i = 0.

The input is terminated by n = 0. Your program must not produce output for it.

Output

For each dataset, print one line.

• If A and B can be uniquely determined, output A and B. Separate the numbers by a single space.
• If there exists more than one possible pair of A and B, output Many (without quotes).
• Otherwise, i.e. if there exists no possible pair, output None (without quotes).

Example

Input

3 2 2 1 49 95351238128934 95351238128934 95351238128932 95351238128936 95351238128936 95351238128936 95351238128960 95351238128900 95351238128896 95351238129096 95351238128772 95351238129096 95351238129096 95351238126156 95351238131712 95351238131712 95351238149576 95351238093388 95351238084040 95351237962316 95351238295552 95351237911684 95351237911684 95351235149824 95351233717380 95351249496652 95351249496652 95351226761216 95351226761216 95351082722436 95351082722436 95352054803020 95352156464260 95348273971200 95348273971200 95354202286668 95356451431556 95356451431556 95346024826312 95356451431556 95356451431556 94557999988736 94256939803780 94256939803780 102741546035788 87649443431880 87649443431880 140737488355328 32684288648324 64 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 11 0 0 1 1 1 0 1 1 1 1 1 63 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 4 1 1 1 1 0

Output

1 4 123456789101112 314159265358979 None 2012 2012 None Many

inputFormat

Input

The input consists of multiple datasets. The number of datasets is no more than 100,000. Each dataset has the following format:

n k_1 k_2 ... k_n

The first line of each dataset contains an integer n (1 \leq n \leq 64). Then n lines follow, each of which contains k_i (0 \leq k_i \leq 2^{63} - 1). For all i > n, k_i = 0.

The input is terminated by n = 0. Your program must not produce

outputFormat

output for it.

Output

For each dataset, print one line.

• If A and B can be uniquely determined, output A and B. Separate the numbers by a single space.
• If there exists more than one possible pair of A and B, output Many (without quotes).
• Otherwise, i.e. if there exists no possible pair, output None (without quotes).

Example

Input

3 2 2 1 49 95351238128934 95351238128934 95351238128932 95351238128936 95351238128936 95351238128936 95351238128960 95351238128900 95351238128896 95351238129096 95351238128772 95351238129096 95351238129096 95351238126156 95351238131712 95351238131712 95351238149576 95351238093388 95351238084040 95351237962316 95351238295552 95351237911684 95351237911684 95351235149824 95351233717380 95351249496652 95351249496652 95351226761216 95351226761216 95351082722436 95351082722436 95352054803020 95352156464260 95348273971200 95348273971200 95354202286668 95356451431556 95356451431556 95346024826312 95356451431556 95356451431556 94557999988736 94256939803780 94256939803780 102741546035788 87649443431880 87649443431880 140737488355328 32684288648324 64 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 11 0 0 1 1 1 0 1 1 1 1 1 63 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 4 1 1 1 1 0

Output

1 4 123456789101112 314159265358979 None 2012 2012 None Many

样例

3
2
2
1
49
95351238128934
95351238128934
95351238128932
95351238128936
95351238128936
95351238128936
95351238128960
95351238128900
95351238128896
95351238129096
95351238128772
95351238129096
95351238129096
95351238126156
95351238131712
95351238131712
95351238149576
95351238093388
95351238084040
95351237962316
95351238295552
95351237911684
95351237911684
95351235149824
95351233717380
95351249496652
95351249496652
95351226761216
95351226761216
95351082722436
95351082722436
95352054803020
95352156464260
95348273971200
95348273971200
95354202286668
95356451431556
95356451431556
95346024826312
95356451431556
95356451431556
94557999988736
94256939803780
94256939803780
102741546035788
87649443431880
87649443431880
140737488355328
32684288648324
64
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
11
0
0
1
1
1
0
1
1
1
1
1
63
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
4
1
1
1
1
0

1 4
123456789101112 314159265358979
None
2012 2012
None
Many

</p>