1의 개수 세기

시간 제한8초메모리 제한256 MB

요약

구간 [A, B]에 속한 수 중에서 각 이진 자릿값이 1인 개수가 주어지면 숨은 A와 B를 복원하고 모호하거나 불가능하면 Many 또는 None을 출력합니다.

난이도: 어려움10점 중 8점
유형: 비트 연산, 수학
정답자: 아직 제출이 없습니다

문제

$b_i(x)$ 를 $x$ 의 아래에서 $i$ 번째 비트, 곧 $x$ 를 2진법으로 나타냈을 때 아래에서 $i$ 번째 자리의 수라고 하자 ( $i \ge 1$ ). 예를 들어 $6 = (110)_2$ 이므로 $b_1(6) = 0$ , $b_2(6) = 1$ , $b_3(6) = 1$ 이고, $i \ge 4$ 인 모든 $i$ 에 대해 $b_i(6) = 0$ 이다.

정수 $A$ 와 $B$ 는 $1 \le A \le B \le 10^{18}$ 을 만족한다. $k_i$ 는 $A \le x \le B$ 이면서 $b_i(x) = 1$ 인 정수 $x$ 의 개수다.

$\{k_i\}$ 가 주어질 때 $A$ 와 $B$ 를 알아내는 프로그램을 작성하라.

입력

입력은 여러 개의 데이터 집합으로 이루어진다. 데이터 집합의 개수는 100,000을 넘지 않는다. 각 데이터 집합의 형식은 다음과 같다.

n
k1
k2
...
kn

각 데이터 집합의 첫 줄에는 정수 $n$ ( $1 \le n \le 64$ )이 주어진다. 이어지는 $n$ 개의 줄에는 각각 $k_i$ ( $0 \le k_i \le 2^{63} - 1$ )가 주어진다. $i > n$ 인 모든 $i$ 에 대해 $k_i = 0$ 이다.

입력의 마지막 줄에는 $n = 0$ 이 주어진다. 이 줄에 대해서는 아무것도 출력하지 않는다.

출력

각 데이터 집합마다 한 줄씩 출력한다.

$A$ 와 $B$ 가 하나로 정해지면 $A$ 와 $B$ 를 공백 하나로 구분해 출력한다.
조건을 만족하는 $(A, B)$ 가 둘 이상이면 Many를 따옴표 없이 출력한다.
조건을 만족하는 $(A, B)$ 가 하나도 없으면 None을 따옴표 없이 출력한다.

예제2

예제 1

입력

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

예제 2

입력

예상 출력

1 1
None
Many
Many