Problem: In the Kingdom of Wakanda, the 2020 economic crisis has made a great impact on each city and its surrounding area. Cities have made a plan to build a fast train rail between them to boost the economy, but because of the insufficient funds, each city can only build a rail with one other city, and they want to do it together.

Cities which are paired up in the plan will share the cost of building the rail between them, and one city might need to pay more than the other. Each city knows the estimated cost of building their part of the rail to every other city. One city can not have the same cost of building the rail with two different cities.

If in a plan, there are two cities that are not connected, but the cost to create a rail between them is lower for each of them than the cost to build the rail with their current pairs, then that plan is not acceptable and the collaboration won't go on. Your task is to create a suitable plan for the cities (pairing of the cities) or say that such plan doesn't exist.

Input

First line contains one integer N \;(2 ≤ N ≤ 10^3)   — the number of cities.

Each of the next N lines contains N-1 integers A_{i,1}, A_{i,2}, ..., A_{i,i-1}, A_{i,i+1}, ..., A_{i,N-1}\; (1 ≤ A_{i,j} ≤ 10^9)   — where A_{i,j} represents the cost for city i to build the rail to city j. Note that in each line A_{i,i} is skipped.

Output

Output should contain N integers O_{1}, O_{2}, ..., O_N, where O_i represents the city with which city i should build the rail with, or -1 if it is not possible to find the stable pairing.

Examples

Input


4
35 19 20
76 14 75
23 43 78
14 76 98


Output


3
4
1
2


Input


4
2 5 8
7 1 12
4 6 7
8 4 5


Output


-1

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using db = double;
using str = string;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;
template <class T>
using V = vector<T>;
template <class T, size_t SZ>
using AR = array<T, SZ>;
const int MOD = 1e9 + 7;
const int MX = 2e5 + 5;
const ll INF = 1e18;
const ld PI = acos((ld)-1);
const int xd[4] = {1, 0, -1, 0}, yd[4] = {0, 1, 0, -1};
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
constexpr int pct(int x) { return __builtin_popcount(x); }
constexpr int bits(int x) { return 31 - __builtin_clz(x); }
ll cdiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); }
ll fdiv(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); }
template <class T>
bool ckmin(T& a, const T& b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
template <class T, class U>
T fstTrue(T lo, T hi, U first) {
  hi++;
  assert(lo <= hi);
  while (lo < hi) {
    T mid = lo + (hi - lo) / 2;
    first(mid) ? hi = mid : lo = mid + 1;
  }
  return lo;
}
template <class T, class U>
T lstTrue(T lo, T hi, U first) {
  lo--;
  assert(lo <= hi);
  while (lo < hi) {
    T mid = lo + (hi - lo + 1) / 2;
    first(mid) ? lo = mid : hi = mid - 1;
  }
  return lo;
}
template <class T>
void remDup(vector<T>& v) {
  sort(begin(v), end(v));
  v.erase(unique(begin(v), end(v)), end(v));
}
template <class T, class U>
void erase(T& t, const U& u) {
  auto it = t.find(u);
  assert(it != end(t));
  t.erase(u);
}
template <class T>
void re(complex<T>& c);
template <class T, class U>
void re(pair<T, U>& p);
template <class T>
void re(vector<T>& v);
template <class T, size_t SZ>
void re(AR<T, SZ>& a);
template <class T>
void re(T& x) {
  cin >> x;
}
void re(db& d) {
  str t;
  re(t);
  d = stod(t);
}
void re(ld& d) {
  str t;
  re(t);
  d = stold(t);
}
template <class T, class... U>
void re(T& t, U&... u) {
  re(t);
  re(u...);
}
template <class T>
void re(complex<T>& c) {
  T a, b;
  re(a, b);
  c = {a, b};
}
template <class T, class U>
void re(pair<T, U>& p) {
  re(p.first, p.second);
}
template <class T>
void re(vector<T>& x) {
  for (auto& a : x) re(a);
}
template <class T, size_t SZ>
void re(AR<T, SZ>& x) {
  for (auto& a : x) re(a);
}
str to_string(char c) { return str(1, c); }
str to_string(const char* second) { return (str)second; }
str to_string(str second) { return second; }
str to_string(bool b) { return to_string((int)b); }
template <class T>
str to_string(complex<T> c) {
  stringstream ss;
  ss << c;
  return ss.str();
}
str to_string(vector<bool> v) {
  str res = "{";
  for (int i = (0); i < ((int)(v).size()); ++i) res += char('0' + v[i]);
  res += "}";
  return res;
}
template <size_t SZ>
str to_string(bitset<SZ> b) {
  str res = "";
  for (int i = (0); i < (SZ); ++i) res += char('0' + b[i]);
  return res;
}
template <class T, class U>
str to_string(pair<T, U> p);
template <class T>
str to_string(T v) {
  bool fst = 1;
  str res = "";
  for (const auto& x : v) {
    if (!fst) res += " ";
    fst = 0;
    res += to_string(x);
  }
  return res;
}
template <class T, class U>
str to_string(pair<T, U> p) {
  return to_string(p.first) + " " + to_string(p.second);
}
template <class T>
void pr(T x) {
  cout << to_string(x);
}
template <class T, class... U>
void pr(const T& t, const U&... u) {
  pr(t);
  pr(u...);
}
void ps() { pr("\n"); }
template <class T, class... U>
void ps(const T& t, const U&... u) {
  pr(t);
  if (sizeof...(u)) pr(" ");
  ps(u...);
}
void DBG() { cerr << "]" << endl; }
template <class T, class... U>
void DBG(const T& t, const U&... u) {
  cerr << to_string(t);
  if (sizeof...(u)) cerr << ", ";
  DBG(u...);
}
void setIn(str second) { freopen(second.c_str(), "r", stdin); }
void setOut(str second) { freopen(second.c_str(), "w", stdout); }
void unsyncIO() { cin.tie(0)->sync_with_stdio(0); }
void setIO(str second = "") {
  unsyncIO();
  if ((int)(second).size()) {
    setIn(second + ".in"), setOut(second + ".out");
  }
}
int N, A[1000][1000];
bool active[1000][1000];
deque<int> pref[1000];
int propose[1000], proposed[1000];
void fin() {
  ps(-1);
  exit(0);
}
void rem(int x, int y) { active[x][y] = active[y][x] = 0; }
void clip(int x) {
  while ((int)(pref[x]).size() && !active[x][pref[x].front()])
    pref[x].pop_front();
  while ((int)(pref[x]).size() && !active[x][pref[x].back()])
    pref[x].pop_back();
  if (!(int)(pref[x]).size()) fin();
}
void ad(int x, int y) {
  propose[x] = y, proposed[y] = x;
  while (1) {
    clip(y);
    if (pref[y].back() != x)
      rem(y, pref[y].back());
    else
      break;
  }
  assert(pref[y].back() == x);
}
int nex(int x) {
  assert((int)(pref[x]).size() > 1);
  int y = pref[x].front();
  pref[x].pop_front();
  clip(x);
  pref[x].push_front(y);
  return proposed[pref[x][1]];
}
int main() {
  setIO();
  re(N);
  if (N & 1) fin();
  for (int i = (0); i < (N); ++i) {
    for (int j = (0); j < (N); ++j)
      if (i != j) {
        re(A[i][j]);
        pref[i].push_back(j);
        active[i][j] = 1;
      }
    sort(begin(pref[i]), end(pref[i]),
         [&](int x, int y) { return A[i][x] < A[i][y]; });
    0;
  }
  for (int i = (0); i < (N); ++i) propose[i] = proposed[i] = -1;
  queue<int> q;
  for (int i = (0); i < (N); ++i) q.push(i);
  while (1) {
    0;
    while ((int)(q).size()) {
      int x = q.front();
      q.pop();
      if (propose[x] != -1) continue;
      0;
      while (1) {
        clip(x);
        int y = pref[x].front();
        if (proposed[y] != -1 && A[y][proposed[y]] < A[y][x]) {
          assert(active[y][x]);
          rem(x, y);
          assert(!active[y][x]);
          continue;
        }
        if (proposed[y] != -1) {
          q.push(proposed[y]);
          propose[proposed[y]] = -1;
          proposed[y] = -1;
        }
        ad(x, y);
        break;
      }
    }
    int st = -1;
    for (int i = (0); i < (N); ++i) {
      clip(i);
      assert(proposed[i] != -1);
      0;
      assert(pref[i].back() == proposed[i]);
      if ((int)(pref[i]).size() > 1) {
        st = i;
        break;
      }
    }
    if (st == -1) {
      for (int i = (0); i < (N); ++i) assert(proposed[propose[i]] == i);
      for (int i = (0); i < (N); ++i) ps(propose[i] + 1);
      exit(0);
    }
    vi cyc;
    {
      int x = st, y = st;
      do {
        x = nex(x), y = nex(nex(y));
      } while (x != y);
      do {
        cyc.push_back(y);
        y = nex(y);
      } while (x != y);
    }
    for (auto& x : cyc) {
      int y = propose[x];
      proposed[y] = -1, propose[x] = -1;
      rem(x, y);
      q.push(x), q.push(y);
    }
  }
}