Description

大家都知道，肯德基里面量大又好吃的东西是薯条和鸡米花，于是藤藤点了一份薯条和一份鸡米花，由于来吃肯德基的小朋友特别多，服务员忙不过来，他直接把薯条和鸡米花一盘端给了藤藤，薯条和鸡米花都是带有数字的，每一根薯条上的数字都是奇数，而鸡米花上的数字都是偶数，藤藤是个有强迫症的吃货，他见不得薯条里混有鸡米花，你能帮他分开一下吗？

Format

Input

第1行为整数n($1 \leq n \leq 1000$)，代表薯条和鸡米花的总数量; 第2行为n个整数，表示薯条或者鸡米花上的数字($1 \leq a_i \leq 1000$)。

Output

输出$4$行.

第$1$行输出薯条的数量$s$,

第$2$行按顺序输出薯条代表的数字(如果s为0则第2行不输出)，用空格隔开，行末无空格。

第$3$行输出鸡米花的数量$j$,

第$4$行按顺序输出鸡米花代表的数字(如果j为0则第4行不输出)，用空格隔开，行末无空格。

Samples

样例输入

10
1 2 3 4 5 6 7 8 9 10

样例输出

5
1 3 5 7 9
5
2 4 6 8 10

Limitation

1s, 1024KiB for each test case.