Two progressions

题意翻译

### 题目描述 等差数列指的是一个任意前后两个元素之间差为定值的非空数列。这个定值被称为公差。例如数列`3,7,11,15`是等差数列。 我们规定任何元素个数为$1$或$2$的数列都是等差数列， 而元素个数为$0$的数列不是等差数列。 给你一个由不同整数$a_1,a_2,\cdots,a_n$组成的数列， 你需要将它分为两个等差数列或确定这是不可能做到的。 在分成两个等差数列的时候元素之间的相对位置不能发生变化。 ### 输入输出格式 #### 输入格式 第一行包含一个正整数$n$表示给定的数列中元素的个数。 第二行共$n$个整数$a_1,a_2,\cdots,a_n(-10^8\le a_i\le 10^8)$， 保证元素之间互不相同。 #### 输出格式 若可以构造，输出两行，每行代表分离出来的一个等差数列。 否则输出`No solution`。

题目描述

An arithmetic progression is such a non-empty sequence of numbers where the difference between any two successive numbers is constant. This constant number is called common difference. For example, the sequence 3, 7, 11, 15 is an arithmetic progression. The definition implies that any sequences whose length equals 1 or 2 are arithmetic and all sequences whose length equals 0 are non-arithmetic. You are given a sequence of different integers $ a_{1},a_{2},...,a_{n} $ . You should either split it into two arithmetic progressions or find out that the operation is impossible to perform. Splitting assigns each member of the given sequence to one of two progressions, but the relative order of numbers does not change. Splitting is an inverse operation to merging.

输入输出格式

输入格式

The first line contains a positive integer $ n $ ( $ 2<=n<=30000 $ ), $ n $ is the length of the given sequence. The second line contains elements of the given sequence $ a_{1},a_{2},...,a_{n} $ ( $ -10^{8}<=a_{i}<=10^{8} $ ). The elements of the progression are different integers.

输出格式

Print the required arithmetic progressions, one per line. The progressions can be positioned in any order. Each progression should contain at least one number. If there's no solution, then print "No solution" (without the quotes)in the only line of the input file. If there are several solutions, print any of them.

输入输出样例

输入样例 #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 

说明

In the second sample another solution is also possible (number three can be assigned to the second progression): 1, 2 and 3, -2, -7.