Tách mảng thành mảng chẵn và mảng lẻ (Split an Array into Even and Odd Arrays)

Nguồn: Phước Hưng OJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho mảng số nguyên $a_0,a_1,\ldots,a_{n-1}$.

Tạo hai mảng theo thứ tự xuất hiện:

• mảng $E$ gồm các phần tử chẵn, tức $a_i\equiv0\pmod2$;
• mảng $O$ gồm các phần tử lẻ, tức $a_i\not\equiv0\pmod2$.

Nếu các chỉ số chẵn là $e_0<e_1<\cdots<e_{p-1}$ thì

Tương tự, nếu các chỉ số lẻ là $o_0<\cdots<o_{q-1}$ thì

Ta có $p+q=n$.

Input

Dòng đầu chứa $n$. Dòng thứ hai chứa $n$ số nguyên $a_i$.

Output

Dòng 1 in $p$ rồi lần lượt các phần tử của $E$. Dòng 2 in $q$ rồi lần lượt các phần tử của $O$. Nếu một nhóm rỗng, dòng tương ứng chỉ chứa số $0$.

Subtask

Subtask 1 (20 điểm): $1\le n\le 10$, $|a_i|\le 10^3$.

Subtask 2 (30 điểm): $1\le n\le 5000$, $|a_i|\le 10^6$.

Subtask 3 (50 điểm): $1\le n\le 2\cdot 10^5$, $|a_i|\le 10^9$.

Ví dụ

Input

7
4 -3 0 9 8 -6 5

Output

4 4 0 8 -6
3 -3 9 5

Giải thích

Các số chẵn theo thứ tự là $4,0,8,-6$; các số lẻ theo thứ tự là $-3,9,5$.