INT_MAX, INT_MIN

Time Limit: 1000 ms

Memory Limit: 32768 ms

Description

Huangwei_njust is having an adventure now. Fortunately, he finds a cave that no one has discovered before. He is sure that there must be some jewellery in the cave. So he happily went in. The cave is full of all kinds of traps and mazes and so on. But as you know, Huang is very brilliant and he has learnt all kinds of algorithms engaged with network flow, graphs, and search skills. So, this can’t trap him. But now he is stopped by a thick door. He can’t open it using any methods. He has found that there are a sequence of numbers on the door, and two blanks to fill in. He doesn’t know what to do.

Then God appears. “This is the last barrier for you and I will tell you what this problem means,” the god said. “You should use these numbers to make a largest number and a smallest one. You have two operations. The first is, you pick any three numbers from the sequence, multiply them, and add the number 1 to the result, and the result will replace the three numbers you choose. The second is, you pick any two numbers, and do as I said as before. When the sequence has only one number, this is the final result. You should find the biggest and the smallest result you could ever make. ” However, Huang is not as excellent at math as he is at other fields. He needs your help. If he succeeds to get the jewellery, he will give some to you as a reward.

Input

There are multiple cases of the input. For each case, the first line contains a number n(3<=n<=1000). Then comes n numbers, which shows the sequence. The input is terminated by n=0. We ensure that all the numbers in the sequence is not smaller than 2 and not greater than 32768.

Output

For each case, output two numbers, which shows the smallest and the largest results. As the result may be very large, print the result module by 9901. So don’t be surprised when you found sometimes the first number of you output is bigger than the second.

Sample Input

3
2 2 2
3
3 2 4
0

Sample Output

9 11
25 29

Hint

Source

HJWAJ

提交代码