算术级数是这样一个非空的数字序列,其中任何两个连续数字之间的差是恒定的。这个常数称为公差。例如,数列3、7、11、15是一个等差数列。该定义意味着任何长度等于 1 或 2 的序列都是算术序列,而所有长度等于 0 的序列都是非算术序列。
给定一个不同整数 a1, a2, ..., an 的序列。您应该将其分成两个算术级数,或者发现该操作无法执行。拆分将给定序列的每个成员分配给两个级数之一,但数字的相对顺序不会改变。拆分是合并的逆操作。
输入
第一行包含一个正整数 n (2 ≤ n ≤ 30000),n 是给定序列的长度。第二行包含给定序列 a1, a2, ..., an (- 108 ≤ ai ≤ 108) 的元素。级数的元素是不同的整数。
输出
打印所需的算术级数,每行一个。进展可以按任何顺序定位。每个级数应至少包含一个数字。如果没有解决方案,则在输入文件的唯一行中打印“无解决方案”(不带引号)。如果有多个解决方案,请打印其中任何一个。
示例
输入 #1
6 4 1 2 7 3 10
输出 #1
1 2 3 4 7 10
输入 #2
5 1 2 3 -2 -7
输出 #2
1 2 3 -2 -7
注意
在第二个示例中,另一种解决方案也是可能的(数字三可以分配给第二个级数):1、2 和 3、-2、-7。