Problem: 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 a1, a2, ..., an. 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.

Input

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 a1, a2, ..., an ( - 108 ≤ ai ≤ 108). The elements of the progression are different integers.

Output

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.

Examples

Input

6
4 1 2 7 3 10


Output

1 2 3 
4 7 10 


Input

5
1 2 3 -2 -7


Output

1 2 3 
-2 -7 

Note

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

Solution (in JAVA):

Solution:
import static java.lang.Math.*;
import java.util.*;
import java.io.*;

public class D {

    public void solve() throws Exception {
        
        int n = nextInt();
        int[] p = nextArr(n);
//      Arrays.sort(p);
        
        LinkedList<Integer> a = new LinkedList<Integer>();
        LinkedList<Integer> b = new LinkedList<Integer>();
        // a a
        int d1 = p[1]-p[0], d2 = INF;
        int last1 = p[1], last2 = INF;
        a.add(p[0]); a.add(p[1]);
        boolean bad = false;
        for (int i=2; i<n; ++i) {
            if (i!=n-1 && p[i]-last1==d1 && ((d2!=INF && p[i]-last2==d2) || (d2==INF && p[i]-last2==p[i+1]-p[i]))) {
                if (p[i+1]-p[i]==d1) {
                    last1 = p[i]; a.add(p[i]);
                }
                else if (p[i+1]-p[i]==d2 || d2==INF) {
                    if (d2==INF) d2=p[i+1]-p[i];
                    last2 = p[i]; b.add(p[i]);
                } else {bad=true; break;}
            }
            else if (p[i]-last1==d1) {
                last1 = p[i];
                a.add(p[i]);
            }
            else if (last2==INF) {
                last2 = p[i];
                b.add(p[i]);
            }
            else if (d2==INF) {
                d2 = p[i]-last2;
                last2 = p[i];
                b.add(p[i]);
            }
            else {
                if (p[i]-last2!=d2) {bad=true; break;}
                last2 = p[i];
                b.add(p[i]);
            }
        }
        if (!bad) out(a,b);
        
        if (n==2) halt("No solution");
        
        a = new LinkedList<Integer>();
        b = new LinkedList<Integer>();
        // a b a
        d1 = p[2]-p[0]; d2 = INF;
        last1 = p[2]; last2 = p[1];
        a.add(p[0]); a.add(p[2]); b.add(p[1]);
        bad = false;
        for (int i=3; i<n; ++i) {
            if (i!=n-1 && p[i]-last1==d1 && ((d2!=INF && p[i]-last2==d2) || (d2==INF && p[i]-last2==p[i+1]-p[i]))) {
                if (p[i+1]-p[i]==d1) {
                    last1 = p[i]; a.add(p[i]);
                }
                else if (p[i+1]-p[i]==d2 || d2==INF) {
                    if (d2==INF) d2=p[i+1]-p[i];
                    last2 = p[i]; b.add(p[i]);
                } else {bad=true; break;}
            }
            else if (p[i]-last1==d1) {
                last1 = p[i];
                a.add(p[i]);
            }
            else if (d2==INF) {
                d2 = p[i]-last2;
                last2 = p[i];
                b.add(p[i]);
            }
            else {
                if (p[i]-last2!=d2) {bad=true; break;}
                last2 = p[i];
                b.add(p[i]);
            }
        }
        if (!bad) out(a,b);
        
        a = new LinkedList<Integer>();
        b = new LinkedList<Integer>();
        // b a a
        d1 = p[2]-p[1]; d2 = INF;
        last1 = p[2]; last2 = p[0];
        a.add(p[1]); a.add(p[2]); b.add(p[0]);
        bad = false;
        for (int i=3; i<n; ++i) {
            if (i!=n-1 && p[i]-last1==d1 && ((d2!=INF && p[i]-last2==d2) || (d2==INF && p[i]-last2==p[i+1]-p[i]))) {
                if (p[i+1]-p[i]==d1) {
                    last1 = p[i]; a.add(p[i]);
                }
                else if (p[i+1]-p[i]==d2 || d2==INF) {
                    if (d2==INF) d2=p[i+1]-p[i];
                    last2 = p[i]; b.add(p[i]);
                } else {bad=true; break;}
            }
            else if (p[i]-last1==d1) {
                last1 = p[i];
                a.add(p[i]);
            }
            else if (d2==INF) {
                d2 = p[i]-last2;
                last2 = p[i];
                b.add(p[i]);
            }
            else {
                if (p[i]-last2!=d2) {bad=true; break;}
                last2 = p[i];
                b.add(p[i]);
            }
        }
        if (!bad) out(a,b);
        
        println("No solution");
        
    }
    
    void out(LinkedList<Integer> a, LinkedList<Integer> b) throws IOException {
//      debug(a,b);
        if (b.isEmpty()) {b.add(new Integer(a.getLast())); a.pollLast();}
        for (Integer i: a) print(i+" ");
        println();
        for (Integer i: b) print(i+" ");
        halt();
    }

    

    ////////////////////////////////////////////////////////////////////////////
    
    boolean showDebug = true;

    double EPS = 1e-7;
    int INF = Integer.MAX_VALUE;
    long INFL = Long.MAX_VALUE;
    double INFD = Double.MAX_VALUE;

    
    int absPos(int num) {
        return num<0 ? 0:num;
    }
    long absPos(long num) {
        return num<0 ? 0:num;
    }
    double absPos(double num) {
        return num<0 ? 0:num;
    }
    
    int min(int... nums) {
        int r = INF;
        for (int i: nums)
            if (i<r) r=i;
        return r;
    }
    int max(int... nums) {
        int r = -INF;
        for (int i: nums)
            if (i>r) r=i;
        return r;
    }
    long minL(long... nums) {
        long r = INFL;
        for (long i: nums)
            if (i<r) r=i;
        return r;
    }
    long maxL(long... nums) {
        long r = -INFL;
        for (long i: nums)
            if (i>r) r=i;
        return r;
    }
    double minD(double... nums) {
        double r = INFD;
        for (double i: nums)
            if (i<r) r=i;
        return r;
    }
    double maxD(double... nums) {
        double r = -INFD;
        for (double i: nums)
            if (i>r) r=i;
        return r;
    }
    
    long sumArr(int[] arr) {
        long res = 0;
        for (int i: arr)
            res+=i;
        return res;
    }
    long sumArr(long[] arr) {
        long res = 0;
        for (long i: arr)
            res+=i;
        return res;
    }
    double sumArr(double[] arr) {
        double res = 0;
        for (double i: arr)
            res+=i;
        return res;
    }

    long partsFitCnt(long partSize, long wholeSize) {
        return (partSize+wholeSize-1)/partSize;
    }

    boolean odd(long num) {
        return (num&1)==1;
    }
    
    boolean hasBit(int num, int pos) {
        return (num&(1<<pos))>0;
    }

    long binpow(int a, int n) {
        long r = 1;
        while (n>0) {
            if ((n&1)!=0) r*=a;
            a*=a;
            n>>=1;
        }
        return r;
    }

    boolean isLetter(char c) {
        return (c>='a' && c<='z') || (c>='A' && c<='Z');
    }
    boolean isLowercase(char c) {
        return (c>='a' && c<='z');
    }
    boolean isUppercase(char c) {
        return (c>='A' && c<='Z');
    }
    boolean isDigit(char c) {
        return (c>='0' && c<='9');
    }
    
    String stringn(String s, int n) {
        if (n<1) return "";
        StringBuilder sb = new StringBuilder(s.length()*n);
        for (int i=0; i<n; ++i) sb.append(s);
        return sb.toString();
    }
    String str(Object o) {
        return o.toString();
    }


    long timer = System.currentTimeMillis();
    void startTimer() {
        timer = System.currentTimeMillis();
    }
    void stopTimer() {
        System.err.println("time: "+(System.currentTimeMillis()-timer)/1000.0);
    }


    class InputReader {
        private byte[] buf;
        private int bufPos = 0, bufLim = -1;
        public InputReader(int size) {
            buf = new byte[size];
        }
        private void fillBuf() throws IOException {
            bufLim = System.in.read(buf);
            bufPos = 0;
        }
        char read() throws IOException {
            if (bufPos>=bufLim) fillBuf(); 
            return (char)buf[bufPos++];
        }
        boolean hasInput() throws IOException {
            if (bufPos>=bufLim) fillBuf();
            return bufPos<bufLim;
        }
    }

    InputReader inputReader = new InputReader(1<<16);
    static BufferedWriter outputWriter = new BufferedWriter(new OutputStreamWriter(System.out), 1<<16);

    char nextChar() throws IOException {
        return inputReader.read();
    }
    char nextNonWhitespaceChar() throws IOException {
        char c = inputReader.read();
        while (c<=' ') c=inputReader.read();
        return c;
    }
    String nextWord() throws IOException {
        StringBuilder sb = new StringBuilder();
        char c = inputReader.read();
        while (c<=' ') c=inputReader.read();
        while (c>' ') {
            sb.append(c);
            c = inputReader.read();
        }
        return new String(sb);
    }
    String nextLine() throws IOException {
        StringBuilder sb = new StringBuilder();
        char c = inputReader.read();
        while (c<=' ') c=inputReader.read();
        while (c!='\n' && c!='\r') {
            sb.append(c);
            c = inputReader.read();
        }
        return new String(sb);
    }
    int nextInt() throws IOException {
        int r = 0;
        char c = nextNonWhitespaceChar();
        boolean neg = false;
        if (c=='-') neg=true;
        else r=c-48;
        c = nextChar();
        while (c>='0' && c<='9') {
            r*=10;
            r+=c-48;
            c=nextChar();
        }
        return neg ? -r:r;
    }
    long nextLong() throws IOException {
        long r = 0;
        char c = nextNonWhitespaceChar();
        boolean neg = false;
        if (c=='-') neg=true;
        else r = c-48;
        c = nextChar();
        while (c>='0' && c<='9') {
            r*=10L;
            r+=c-48L;
            c=nextChar();
        }
        return neg ? -r:r;
    }
    double nextDouble() throws NumberFormatException, IOException {
        return Double.parseDouble(nextWord());
    }
    int[] nextArr(int size) throws NumberFormatException, IOException {
        int[] arr = new int[size];
        for (int i=0; i<size; ++i)
            arr[i] = nextInt();
        return arr;
    }
    long[] nextArrL(int size) throws NumberFormatException, IOException {
        long[] arr = new long[size];
        for (int i=0; i<size; ++i)
            arr[i] = nextLong();
        return arr;
    }
    double[] nextArrD(int size) throws NumberFormatException, IOException {
        double[] arr = new double[size];
        for (int i=0; i<size; ++i)
            arr[i] = nextDouble();
        return arr;
    }
    String[] nextArrS(int size) throws NumberFormatException, IOException {
        String[] arr = new String[size];
        for (int i=0; i<size; ++i)
            arr[i] = nextWord();
        return arr;
    }
    char[] nextArrCh(int size) throws IOException {
        char[] arr = new char[size];
        for (int i=0; i<size; ++i)
            arr[i] = nextNonWhitespaceChar();
        return arr;
    }
    char[][] nextArrCh(int rows, int columns) throws IOException {
        char[][] arr = new char[rows][columns];
        for (int i=0; i<rows; ++i)
            for (int j=0; j<columns; ++j)
                arr[i][j] = nextNonWhitespaceChar();
        return arr;
    }
    char[][] nextArrChBorders(int rows, int columns, char border) throws IOException {
        char[][] arr = new char[rows+2][columns+2];
        for (int i=1; i<=rows; ++i)
            for (int j=1; j<=columns; ++j)
                arr[i][j] = nextNonWhitespaceChar();
        for (int i=0; i<columns+2; ++i) {
            arr[0][i] = border;
            arr[rows+1][i] = border;
        }
        for (int i=0; i<rows+2; ++i) {
            arr[i][0] = border;
            arr[i][columns+1] = border;
        }
        return arr;
    }

    void printf(String format, Object... args) throws IOException {
        outputWriter.write(String.format(format, args));
    }
    void print(Object o) throws IOException {
        outputWriter.write(o.toString());
    }
    void println(Object o) throws IOException {
        outputWriter.write(o.toString());
        outputWriter.newLine();
    }
    void print(Object... o) throws IOException {
        for (int i=0; i<o.length; ++i) {
            if (i!=0) outputWriter.write(' ');
            outputWriter.write(o[i].toString());
        }
    }
    void println(Object... o) throws IOException {
        print(o);
        outputWriter.newLine();
    }
    void printn(Object o, int n) throws IOException {
        String s = o.toString();
        for (int i=0; i<n; ++i) {
            outputWriter.write(s);
            if (i!=n-1) outputWriter.write(' ');
        }
    }
    void printnln(Object o, int n) throws IOException {
        printn(o, n);
        outputWriter.newLine();
    }
    void printArr(int[] arr) throws IOException {
        for (int i=0; i<arr.length; ++i) {
            if (i!=0) outputWriter.write(' ');
            outputWriter.write(Integer.toString(arr[i]));
        }
    }
    void printArr(long[] arr) throws IOException {
        for (int i=0; i<arr.length; ++i) {
            if (i!=0) outputWriter.write(' ');
            outputWriter.write(Long.toString(arr[i]));
        }
    }
    void printArr(double[] arr) throws IOException {
        for (int i=0; i<arr.length; ++i) {
            if (i!=0) outputWriter.write(' ');
            outputWriter.write(Double.toString(arr[i]));
        }
    }
    void printArr(String[] arr) throws IOException {
        for (int i=0; i<arr.length; ++i) {
            if (i!=0) outputWriter.write(' ');
            outputWriter.write(arr[i]);
        }
    }
    void printArr(char[] arr) throws IOException {
        for (char c: arr) outputWriter.write(c);
    }
    void printlnArr(int[] arr) throws IOException {
        printArr(arr);
        outputWriter.newLine();
    }
    void printlnArr(long[] arr) throws IOException {
        printArr(arr);
        outputWriter.newLine();
    }
    void printlnArr(double[] arr) throws IOException {
        printArr(arr);
        outputWriter.newLine();
    }
    void printlnArr(String[] arr) throws IOException {
        printArr(arr);
        outputWriter.newLine();
    }
    void printlnArr(char[] arr) throws IOException {
        printArr(arr);
        outputWriter.newLine();
    }
    void halt(Object... o) throws IOException {
        if (o.length!=0) println(o);
        outputWriter.flush(); outputWriter.close();
        System.exit(0);
    }
    
    void debug(Object... o) {
        if (showDebug) System.err.println(Arrays.deepToString(o));
    }


    public static void main(String[] args) throws Exception {
        Locale.setDefault(Locale.US);
        new D().solve();
        outputWriter.flush(); outputWriter.close();
    }
}