Tách âm - zero - dương vào ba mảng (Split Negative, Zero, and Positive Values)

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ách mảng thành ba dãy con ổn định:

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

trong đó mỗi dãy giữ nguyên thứ tự xuất hiện của các phần tử trong mảng ban đầu.

Gọi kích thước ba dãy lần lượt là $n_-$, $n_0$, $n_+$. Khi đó

$$n_-+n_0+n_+=n.$$

Input

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

Output

In ba dòng theo thứ tự nhóm âm, nhóm bằng $0$, nhóm dương. Mỗi dòng bắt đầu bằng kích thước logic của nhóm, sau đó là các phần tử của nhóm; nhóm rỗng chỉ in 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

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

Output

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

Giải thích

Các phần tử được phân vào đúng ba nhóm theo dấu và thứ tự trong từng nhóm không thay đổi.