题目描述
已知由n(n≥2)个正整数构成的集合A={ak}（0≤k<n），将其划分为两个不相交的子集A1和A2，元素个数分别是n1和n2，A1和A2中元素之和分别为S1和S2。设计一个尽可能高效的划分算法，满足|n1-n2|最小且|S1-S2|最大。
输入
多组数据，每组数据两行。第一行为一个整数n，代表数组中有n个元素。第二行为数组中的n个元素（元素之间用空格分隔）。当n等于0时，输入结束。
输出
每组数据输出两行。第一行为子集A1，第二行为子集A2，每两个元素用空格分隔。
样例输入 Copy
4
1 2 3 4
5
9 8 1 1 1
0
样例输出 Copy
1 2
3 4
1 1
1 8 9