Simran is at a casino with his friend Apoorv. His friend Apoorv challenged him to solve a problem. Apoorv gave him N stacked cards on the pile. Each card has a number written on it. Then Apoorv asked Q iterations/queries from Simran. Apoorv Created a rule as -In ith iteration/query, Simran can start picking up the cards in the Ai-1th pile from the top one by one and check whether the number written on the card is divisible by the ith prime number. If the number is divisible, Simran will stack that card on pile Bi. Otherwise, he stacks that card on pile Ai. After Q iterations, cards can only be on pile B1, B2, B3, . . . BQ, AQ. Apoorv wants Simran to find Output numbers on these cards from top to bottom of each pile in order of B1, B2, B3, . . . BQ, AQ.
Simran is unable to find the Output Numbers. He needs your help. Please help Simran to win the challenge.

Input Format
The First line contains N and Q. The next line contains N space-separated integers representing the initial pile of cards i.e., A0. The leftmost value represents the bottom card of the pile.

Constraints
N < 10^5
Q < 10^5
|Ai| < 10^9

Output
Output N lines, each line containing the number written on the card.