The Market

The residents of nearby villages come to the city's market to make purchases. There are ~N~ villages around the city. The residents of the first village go to the city every ~x_i~ days for supplies, those of the second village every ~x_2~ days, and so on. Today, the residents of all villages happened to meet at the city's market - this happens quite rarely. Find after how many days the residents of at least ~N - 1~ villages will meet again at the city's market.

Problem

Develop a program in one of the IOI languages (PASCAL, C, C++, Java) that, after reading the number of villages and the frequency of their residents' visits to the city's market, will find the minimum number of days after which the residents of at least ~N - 1~ villages will meet again. If on that day the residents of one village are absent, your program should also determine which village is missing.

Input Files

The input files named agora.in are text files with the following structure: The first line contains an integer ~N~, the number of villages (1 ~\le~ N ~\le~ 1.000.000). The second line contains ~N~ positive integers ~\mathbf{x_i}~, separated in pairs by a space. Each number ~x_i~ (1 ~\le~ ~x_i~ ~\le~ 1.000.000) represents how often the residents of the ~i~-th village come to the city's market (i.e. every ~3~ days). Assume that the residents of all villages will meet again at the city's market at most in ~10^{18}~ days (a value too large to be represented by a 32-bit integer).

Output Files

The output files named agora.out are text files with the following structure: They have exactly one line containing exactly two integers. The first is the requested number of days after which at least ~N - 1~ villages' residents will meet again at the city's market. The second number is zero ~(0)~ if on that day the residents of all villages will meet again. Otherwise, it is the increasing number of the village whose residents will be absent. (Villages are numbered from ~1~ to ~N~.)

Examples of Input - Output Files

1st

STDIN (agora.in)

10
1 2 3 4 5 6 7 8 9 10

STDOUT (agora.out)

360 7

In this example, after ~360~ days, the residents of all villages will meet again, except for the ~7~th village.

2nd

STDIN (agora.in)

9
10 14 15 30 21 5 40 4 8

STDOUT (agora.out)

840 0

In this example, after ~840~ days, the residents of all villages will meet again. No previous day will have the residents of at least ~8~ villages meeting.

3d

STDIN (agora.in)

5
25065 3575 12305 88590 1758

STDOUT (agora.out)

25845383485350 4

In this example, where it seems that the villagers are immortal and also don't eat much, the residents of four villages (excluding the ~4~th) will meet again after ~25.845.383.485.350~ days (more than twenty-five quadrillion!).

Notes:

Formatting: In both the input and the output, each line terminates with a newline character.
Maximum execution time: 1 sec.
Maximum available memory: 64 MB.
Headers in the source code: At the beginning of your source code, you should use the following headers.

(* USER: username
LANG: PASCAL
TASK: agora *)

for PASCAL coders

/* USER: username
LANG: C
TASK: agora */

for C coders

/* USER: username
LANG: C++
TASK: agora */

for C++ coders

/* USER: username
LANG: Java
TASK: agora */

for Java coders

# USER: username
# LANG: Python
# TASK: agora

for Python coders