ALWFACT - Allowed Factors


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 ≤ 102) and M (1 ≤ M ≤ 105) representing respectively the number of numbers written by Professor Chico and the number written on the card. The second line contains N prime numbers Pi (2 ≤ Pi < 106), where Pi (1 ≤ iN) 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


hide comments
David: 2021-02-02 20:18:16

First Java AC!

Scape: 2020-06-17 18:06:22

This problem is a joke. Horrible statement (thanks @smso for clearing it up), weak input and no clarifications on the number of test cases.

What should be the output for this? You can bet there won't be cases like this because the answer doesn't fit even in long long.

100 100000
<insert 100 prime numbers from 10^6 to downwards>
0 0

I have the worst runtime, but my program can crunch the following input under seconds where as most AC programs online give TLE on this -.-


100 100000
<insert first 100 primes>
0 0

smso: 2019-09-26 08:00:24

Clearer statement:
"A non-decreasing sequence is formed from product of any power and any number of a given set of primes. You have to find the Mth term."

Last edit: 2019-09-26 08:01:37
pallindromeguy: 2019-07-03 21:07:43

sorting the prime numbers in desc order gives AC and in ascending order gives TLE. Any reason why?

julkas: 2018-06-03 11:46:46

Good problem and interesting results.

absolute_coder: 2018-05-28 15:03:20

could you tell ..No of test case ?


Added by:Francisco Elio Parente Arcos Filho [UEA]
Date:2018-05-21
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: SQLITE