Chico told his students that now they would be referenced by numerical codes of up to 12 digits in official communications (e-mails and tasks). And then he gave to each one of his students a card containing an unique number written on it. Quickly the students assumed that this would be their code, but to the surprise of the students and Levi's despair, Professor Chico explained that these were not their code.

A student's code was the term of an ordered sequence S that was in the position (indexed from 1) specified by the number on the card of each student. This sequence has a special feature: each term, when decomposed into prime factors, can only have numbers contained in a set of N elements written on the board by the teacher. And to make life even harder for Levi, those numbers would change every week in such a way that he will always have to recalculate his code if he doesn't want to delay his tasks.

Your task is to make a program to help Levi, so that given the prime numbers written on the board during the week by Professor Chico and number on the card, tell his weekly code.

Input

The input consists of several test cases. The first line of a test case contains two integers N (1 ≤ N ≤ 10²) and M (1 ≤ M ≤ 10⁵) representing respectively the number of numbers written by Professor Chico and the number written on the card. The second line contains N prime numbers P_i (2 ≤ P_i < 10⁶), where P_i (1 ≤ i ≤ N) is a number written in the board. The entry ends when N=M=0.

Output

The output consists of one line per test case containing the Levi's weekly code.

Example

Input:
2 1
2 3
2 10
2 3
3 10
2 3 5
3 10
3 7 13
0 0
Output:
2
24
15
81