Split Negative, Zero, and Positive Values

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem

Given $a_0,a_1,\ldots,a_{n-1}$, split it into three stable subsequences:

$$N=[a_i\mid a_i<0],\qquad Z=[a_i\mid a_i=0],\qquad P=[a_i\mid a_i>0].$$

Each subsequence preserves original order, and their sizes sum to $n$.

Input

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

Output

Print three lines for negative, zero, and positive groups. Each line starts with its logical size followed by its elements; 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

8
-4 0 7 -1 0 3 -9 2

Output

3 -4 -1 -9
2 0 0
3 7 3 2

Explanation

The output follows directly from the mathematical definition above.