Cho một số nguyên dương x, hãy phân tích x thành thừa số nguyên tố và in các thừa số theo thứ tự tăng dần.

Với nhiều truy vấn, hãy tiền xử lý SPF (Smallest Prime Factor — thừa số nguyên tố nhỏ nhất) cho tất cả các số từ 1 đến N bằng sàng số học (linear sieve), sau đó trả lời mỗi truy vấn trong O(log x).

Đầu vào

• Dòng đầu tiên gồm hai số nguyên N (1 ≤ N ≤ 10^6) và Q (1 ≤ Q ≤ 10^5).
• Dòng thứ hai gồm Q số nguyên x (1 ≤ x ≤ N).

Đầu ra

Gồm Q dòng, mỗi dòng là phân tích thừa số nguyên tố của x theo dạng x = p1^e1 * p2^e2 * .... Nếu x = 1, in 1 = 1.

Ví dụ

Input:
20 4
12 17 18 1

Output:
12 = 2^2 * 3
17 = 17
18 = 2 * 3^2
1 = 1