Counting 1's

Time limit8sMemory limit256 MB

Summary

Given how many numbers in the hidden interval [A, B] have each binary bit set, recover A and B or report Many or None.

Level: Hard8 of 10
Topics: Bit manipulation, Math
Solved: No attempts yet

Problem

Let $b_i(x)$ be the $i$ -th least significant bit of $x$ , that is, the $i$ -th least significant digit of $x$ written in base 2 ( $i \ge 1$ ). For example, $6 = (110)_2$ , so $b_1(6) = 0$ , $b_2(6) = 1$ , $b_3(6) = 1$ , and $b_i(6) = 0$ for every $i \ge 4$ .

The integers $A$ and $B$ satisfy $1 \le A \le B \le 10^{18}$ . Let $k_i$ be the number of integers $x$ with $A \le x \le B$ and $b_i(x) = 1$ .

Given $\{k_i\}$ , determine $A$ and $B$ .

Input

The input consists of several datasets. The number of datasets is at most 100,000. Each dataset has this format:

n
k1
k2
...
kn

The first line of a dataset contains the integer $n$ ( $1 \le n \le 64$ ). Each of the next $n$ lines contains one $k_i$ ( $0 \le k_i \le 2^{63} - 1$ ). For every $i > n$ , $k_i = 0$ .

The last line of the input contains $n = 0$ . Print nothing for that line.

Output

Print one line for each dataset.

If $A$ and $B$ are uniquely determined, print $A$ and $B$ separated by a single space.
If more than one pair $(A, B)$ fits, print Many without the quotes.
If no pair $(A, B)$ fits, print None without the quotes.

Examples2

Example 1

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

Expected output

1 4
123456789101112 314159265358979
None
2012 2012
None
Many

Example 2

Input

Expected output

1 1
None
Many
Many