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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
inline void pisz(int n) { printf("%d\n", n); }
const int dr[4] = {-1, 0, 1, 0};
const int dc[4] = {0, -1, 0, 1};
const int drr[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dcc[8] = {0, -1, -1, -1, 0, 1, 1, 1};
template <typename T, typename TT>
ostream& operator<<(ostream& s, pair<T, TT> t) {
  return s << "(" << t.first << "," << t.second << ")";
}
template <typename T>
ostream& operator<<(ostream& s, vector<T> t) {
  for (int i = 0; i < ((int)((t).size())); i++) s << t[i] << " ";
  return s;
}
class UnionFind {
 private:
  vector<int> rank, p;

 public:
  UnionFind(int n) {
    for (int i = 0; i < n; i++) p.push_back(i);
    rank.assign(n, 0);
  }
  int findSet(int s) { return (p[s] == s) ? s : (p[s] = findSet(p[s])); }
  bool isSameSet(int i, int j) { return findSet(i) == findSet(j); }
  void unionSet(int i, int j) {
    if (isSameSet(i, j)) return;
    int x = findSet(i), y = findSet(j);
    if (rank[x] > rank[y])
      p[y] = x;
    else {
      p[x] = y;
      if (rank[x] == rank[y]) rank[y]++;
    }
  }
};
bool fcomp(double A, double B) {
  double EPSILON = numeric_limits<double>::epsilon();
  double diff = A - B;
  return fabs(diff) < EPSILON;
}
double x_y(int x1, int y1, int x2, int y2) {
  return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
vector<long long> v1, v2;
map<int, int> have, tmp, id;
long long dt[30050];
int n;
int ck() { return 0; }
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%lld", &dt[i]);
    have[i] = 1;
    id[dt[i]] = i;
  }
  if (n == 2) {
    cout << dt[0] << endl;
    cout << dt[1] << endl;
    return 0;
  }
  int ys = 1;
  long long diff1 = dt[2] - dt[0], diff2 = INT_MAX;
  v1.push_back(dt[0]);
  v1.push_back(dt[2]);
  v2.push_back(dt[1]);
  for (int i = 3; i < n; i++) {
    if (v2.size() > 1) diff2 = v2[1] - v2[0];
    if (i == n - 1) {
      if (diff2 == INT_MAX) {
        v2.push_back(dt[i]);
        continue;
      }
      if (dt[i] - v1.back() == diff1)
        v1.push_back(dt[i]);
      else if (dt[i] - v2.back() == diff2)
        v2.push_back(dt[i]);
      else
        ys = 0;
      continue;
    }
    long long nxt = dt[i + 1] - dt[i];
    int ok1 = (dt[i] - v1.back() == diff1),
        ok2 = (diff2 == INT_MAX || (dt[i] - v2.back() == diff2));
    if (!ok1 && !ok2) {
      ys = 0;
      continue;
    }
    if (!ok1) {
      v2.push_back(dt[i]);
    } else if (!ok2) {
      v1.push_back(dt[i]);
    } else {
      if (nxt == diff1 || (v2.size() == 1 && nxt != dt[i] - v2[0])) {
        v1.push_back(dt[i]);
      } else
        v2.push_back(dt[i]);
    }
  }
  if (ys) {
    for (int jk = 0; jk <= v1.size() - 1; jk++)
      cout << v1[jk] << (jk == v1.size() - 1 ? '\n' : ' ');
    for (int jk = 0; jk <= v2.size() - 1; jk++)
      cout << v2[jk] << (jk == v2.size() - 1 ? '\n' : ' ');
    return 0;
  }
  ys = 1;
  v1.clear();
  v2.clear();
  diff1 = INT_MAX;
  diff2 = dt[2] - dt[1];
  v1.push_back(dt[0]);
  v2.push_back(dt[1]);
  v2.push_back(dt[2]);
  for (int i = 3; i < n; i++) {
    if (v1.size() > 1) diff1 = v1[1] - v1[0];
    if (i == n - 1) {
      if (diff1 == INT_MAX) {
        v1.push_back(dt[i]);
        continue;
      }
      if (dt[i] - v1.back() == diff1)
        v1.push_back(dt[i]);
      else if (dt[i] - v2.back() == diff2)
        v2.push_back(dt[i]);
      else
        ys = 0;
      continue;
    }
    long long nxt = dt[i + 1] - dt[i];
    int ok2 = (dt[i] - v2.back() == diff2),
        ok1 = (diff1 == INT_MAX || (dt[i] - v1.back() == diff1));
    if (!ok1 && !ok2) {
      ys = 0;
      continue;
    }
    if (!ok1) {
      v2.push_back(dt[i]);
    } else if (!ok2) {
      v1.push_back(dt[i]);
    } else {
      if (nxt == diff2 || (v1.size() == 1 && nxt != dt[i] - v1[0])) {
        v2.push_back(dt[i]);
      } else
        v1.push_back(dt[i]);
    }
  }
  if (ys) {
    for (int jk = 0; jk <= v1.size() - 1; jk++)
      cout << v1[jk] << (jk == v1.size() - 1 ? '\n' : ' ');
    for (int jk = 0; jk <= v2.size() - 1; jk++)
      cout << v2[jk] << (jk == v2.size() - 1 ? '\n' : ' ');
    return 0;
  }
  ys = 1;
  v1.clear();
  v2.clear();
  diff1 = dt[1] - dt[0];
  diff2 = INT_MAX;
  v1.push_back(dt[0]);
  v1.push_back(dt[1]);
  for (int i = 2; i < n; i++) {
    if (v2.size() > 1) diff2 = v2[1] - v2[0];
    if (i == n - 1) {
      if (diff2 == INT_MAX) {
        v2.push_back(dt[i]);
        continue;
      }
      if (dt[i] - v1.back() == diff1)
        v1.push_back(dt[i]);
      else if (dt[i] - v2.back() == diff2)
        v2.push_back(dt[i]);
      else
        ys = 0;
      continue;
    }
    long long nxt = dt[i + 1] - dt[i];
    int ok1 = (dt[i] - v1.back() == diff1),
        ok2 = (diff2 == INT_MAX || (dt[i] - v2.back() == diff2));
    if (!ok1 && !ok2) {
      ys = 0;
      continue;
    }
    if (!ok1) {
      v2.push_back(dt[i]);
    } else if (!ok2) {
      v1.push_back(dt[i]);
    } else {
      if (nxt == diff1 || v2.empty() ||
          (v2.size() == 1 && nxt != dt[i] - v2[0])) {
        v1.push_back(dt[i]);
      } else
        v2.push_back(dt[i]);
    }
  }
  if (ys) {
    if (v2.empty()) {
      v2.push_back(v1.back());
      v1.pop_back();
    }
    for (int jk = 0; jk <= v1.size() - 1; jk++)
      cout << v1[jk] << (jk == v1.size() - 1 ? '\n' : ' ');
    for (int jk = 0; jk <= v2.size() - 1; jk++)
      cout << v2[jk] << (jk == v2.size() - 1 ? '\n' : ' ');
    return 0;
  }
  cout << "No solution" << endl;
  return 0;
}