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 \le N \le 10^6\)) và Q (\(1 \le Q \le 10^5\)).
• Dòng thứ hai gồm Q số nguyên x (\(1 \le x \le 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

Ràng buộc & Subtasks