Tạo Mảng

Trong một buổi thảo luận về triết học, FullHouse Dev đã đặt ra một câu hỏi thú vị về bản chất của trật tự và hỗn độn. Họ quyết định minh họa điều này thông qua một bài toán về việc sắp xếp các số nguyên vào hàng đợi và ngăn xếp, nơi mà trật tự và quy luật được thể hiện qua các số nguyên tố, còn sự phức tạp được biểu diễn qua các số hợp.

Bài toán

Cho một mảng \(A\) gồm \(n\) số nguyên. Nhiệm vụ là tạo một hàng đợi chứa các số nguyên tố và một ngăn xếp chứa các số hợp. Quy tắc để tạo ngăn xếp và hàng đợi là phải có thể tái tạo lại được mảng ban đầu bằng cách sử dụng các thao tác pop và dequeue.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(n\) - số lượng phần tử trong mảng.
• Dòng thứ hai chứa \(n\) số nguyên cách nhau bởi dấu cách - các phần tử của mảng \(A\).

OUTPUT FORMAT:

• Dòng đầu tiên in ra các phần tử trong hàng đợi.
• Dòng thứ hai in ra các phần tử trong ngăn xếp.

Ràng buộc:

• \(1 \leq n \leq 10^5\)
• \(1 \leq A[i] \leq 10^9\)

Ví dụ

INPUT

5
7 21 18 3 12

OUTPUT

7 3
12 18 21

Giải thích

Với mảng đầu vào \(A\) gồm 5 số: 7, 21, 18, 3, 12:

• Hàng đợi chứa các số nguyên tố: 7, 3
• Ngăn xếp chứa các số hợp: 12, 18, 21

Ta có thể tái tạo lại mảng ban đầu bằng cách:

1. Lấy từ hàng đợi: 7
2. Lấy từ ngăn xếp: 21
3. Lấy từ ngăn xếp: 18
4. Lấy từ hàng đợi: 3
5. Lấy từ ngăn xếp: 12

Kết quả thu được chính là mảng ban đầu: 7, 21, 18, 3, 12