Prime Factorization

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Factor integer n≥2 into prime factors in nondecreasing order, repeating each factor according to its multiplicity.

Input

One integer n.

Output

One space-separated sorted list of prime factors.

Subtasks

• Subtask 1 (20%): n ≤ 1000.

• Subtask 2 (30%): n ≤ 10^8.

• Subtask 3 (50%): n ≤ 10^12.

Examples

Example 1

Input:

72

Output:

2 2 2 3 3

Explanation: 72 factors into 2,2,2,3,3.

Example 2

Input:

97

Output:

97

Explanation: 97 is prime.

Example 3

Input:

2

Output:

2

Explanation: 2 is the smallest prime.