H. Yet Another Maximize GCD Problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ with size $$$n$$$ and an integer $$$k$$$; you can do the following operation:

1. Choose two indices $$$i, j$$$.

2. Choose a positive prime factor of $$$a_i$$$, denote it $$$x$$$.

3. Multiply $$$a_j$$$ by $$$x$$$, divide $$$a_i$$$ by $$$x$$$.

For each $$$i$$$ from $$$1$$$ to $$$k$$$, answer the following query:

What is the maximum GCD of the array after $$$i$$$ operations?

Input

The first line contains two integers $$$n, k$$$ $$$(1 \leq n,k \leq 10^5)$$$.

The second line contains $$$n$$$ integers $$$a_i$$$ $$$(1 \leq a_i \leq 10^6)$$$.

—

Tests in subtasks are numbered from $$$1-25$$$ with samples skipped. Each test is worth $$$\frac{100}{25}=4$$$ points.

Tests $$$1-5$$$ satisfy $$$n,k \leq 200$$$.

Tests $$$6-10$$$ satisfy that each $$$a_i$$$ has at most $$$2$$$ distinct prime factors.

Tests $$$11-25$$$ satisfy no additional constraints.

Output

One line with $$$k$$$ integers; the $$$i$$$-th integer denotes the answer after $$$i$$$ operations.

Example
Input
4 5
900 150 6 1
Output
3 6 15 30 30
Note

Initially, the array is:

$$$[900, 150, 6, 1]$$$

We describe one possible way to achieve the optimal answers.

After 1 operation: $$$[300, 150, 6, 3]$$$

After 2 operations: $$$[150, 150, 6, 6]$$$

After 3 operations: $$$[60, 30, 30, 15]$$$

After 4 operations: $$$[30, 30, 30, 30]$$$

After 5 operations: $$$[30, 30, 30, 30]$$$

—

Problem Idea: naturalselection

Problem Preparation: naturalselection

Occurrences: Novice H, Advanced D