No tag edit access

E. Divisors

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputBizon the Champion isn't just friendly, he also is a rigorous coder.

Let's define function *f*(*a*), where *a* is a sequence of integers. Function *f*(*a*) returns the following sequence: first all divisors of *a*_{1} go in the increasing order, then all divisors of *a*_{2} go in the increasing order, and so on till the last element of sequence *a*. For example, *f*([2, 9, 1]) = [1, 2, 1, 3, 9, 1].

Let's determine the sequence *X*_{i}, for integer *i* (*i* ≥ 0): *X*_{0} = [*X*] ([*X*] is a sequence consisting of a single number *X*), *X*_{i} = *f*(*X*_{i - 1}) (*i* > 0). For example, at *X* = 6 we get *X*_{0} = [6], *X*_{1} = [1, 2, 3, 6], *X*_{2} = [1, 1, 2, 1, 3, 1, 2, 3, 6].

Given the numbers *X* and *k*, find the sequence *X*_{k}. As the answer can be rather large, find only the first 10^{5} elements of this sequence.

Input

A single line contains two space-separated integers — *X* (1 ≤ *X* ≤ 10^{12}) and *k* (0 ≤ *k* ≤ 10^{18}).

Output

Print the elements of the sequence *X*_{k} in a single line, separated by a space. If the number of elements exceeds 10^{5}, then print only the first 10^{5} elements.

Examples

Input

6 1

Output

1 2 3 6

Input

4 2

Output

1 1 2 1 2 4

Input

10 3

Output

1 1 1 2 1 1 5 1 1 2 1 5 1 2 5 10

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/18/2017 03:07:36 (c4).

Desktop version, switch to mobile version.

User lists

Name |
---|