eolymp
bolt
Try our new interface for solving problems
Problems

Counting 1`s

Counting 1`s

Time limit 4 seconds
Memory limit 256 MiB

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 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 (1 A B 10^18) be integers, and k_i be the number of integers x such that A x B and b_i(x) = 1.

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

Input data

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

n

k_1

k_2

...

k_n

The first line of each dataset contains an integer n (1 n 64). Then n lines follow, each of which contains k_i (0 k_i2^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 data

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).

Examples

Input example #1
3
2
2
1
4
1
1
1
1
0
Output example #1
1 4
Many
Source 2012 JAG Practice Contest for ACM-ICPC Asia Regional 2012, AtCoder, November 4; 2013 Petrozavodsk Winter Training Camp, January 26, Problem B