Split an Array into Even and Odd Arrays

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem

Given $a_0,a_1,\ldots,a_{n-1}$, create two arrays in original order: $E$ contains all even values ($a_i\equiv0\pmod2$), and $O$ contains all odd values. Their logical sizes are $p$ and $q$ with $p+q=n$.

Input

The first line contains $n$. The second line contains $n$ integers $a_i$.

Output

Line 1 prints $p$ followed by all elements of $E$. Line 2 prints $q$ followed by all elements of $O$. An empty group is printed as just 0.

Subtask

Subtask 1 (20 points): $1\le n\le 10$, $|a_i|\le 10^3$.

Subtask 2 (30 points): $1\le n\le 5000$, $|a_i|\le 10^6$.

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

Example

Input

7
4 -3 0 9 8 -6 5

Output

4 4 0 8 -6
3 -3 9 5

Explanation

The output follows directly from the mathematical definition above.