Problem: Functional graph is a directed graph in which all vertices have outdegree equal to 1. Loops are allowed.

Some vertices of a functional graph lay on a cycle. From the others we can come to a cycle by making a finite number of steps along the edges (we consider only finite functional graphs in this problem).

Let's compute two values for each vertex. precyclei is the amount of edges we should pass to get to a vertex which is a part of some cycle (zero, if i itself lies on a cycle), cyclei is the length of the cycle we get to.

You are given the information about these values for some functional graph. For each vertex you know the values precyclei and cyclei, however, instead of some values there can be the question mark. It means that these values are unknown.

Build any functional graph that suits the description or determine that there is no such graph.

Input

The first line contains single integer n (1 ≤ n ≤ 300) — the number of vertices in the graph.

Each of the next n lines contain two integers — precyclei (0 ≤ precyclei ≤ n - 1) and cyclei (1 ≤ cyclei ≤ n). There could be question marks instead of some of these values.

Output

In case there is no solution, print -1.

Otherwise, print n integers. i-th of them is the number of vertex to which the edge form the i-th vertex go.

The vertices should be in the same order as they go in input data.

If there are multiple solutions, print any of them.

Examples

Input

3
0 3
0 3
? ?


Output

2 3 1 


Input

5
3 2
? ?
? ?
? ?
? ?


Output

5 3 2 2 4 


Input

8
? 3
? ?
0 2
0 2
0 3
0 3
0 3
3 3


Output

5 1 4 3 6 7 5 2 


Input

1
? ?


Output

1 


Input

6
0 3
0 3
0 3
0 3
0 3
0 3


Output

2 3 1 5 6 4 


Input

2
1 1
1 1


Output

-1

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
template <typename T, typename U>
std::istream &operator>>(std::istream &i, pair<T, U> &p) {
  i >> p.first >> p.second;
  return i;
}
template <typename T>
std::istream &operator>>(std::istream &i, vector<T> &t) {
  for (auto &v : t) {
    i >> v;
  }
  return i;
}
template <typename T, typename U>
std::ostream &operator<<(std::ostream &o, const pair<T, U> &p) {
  o << p.first << ' ' << p.second;
  return o;
}
template <typename T>
std::ostream &operator<<(std::ostream &o, const vector<T> &t) {
  if (t.empty()) o << '\n';
  for (size_t i = 0; i < t.size(); ++i) {
    o << t[i] << " \n"[i == t.size() - 1];
  }
  return o;
}
template <typename T>
using minheap = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
using maxheap = priority_queue<T, vector<T>, less<T>>;
unsigned int logceil(long long first) {
  return first ? 8 * sizeof(long long) - __builtin_clzll(first) : 0;
}
namespace std {
template <typename T, typename U>
struct hash<pair<T, U>> {
  hash<T> t;
  hash<U> u;
  size_t operator()(const pair<T, U> &p) const {
    return t(p.first) ^ (u(p.second) << 7);
  }
};
}  // namespace std
template <typename T, typename F>
T bsh(T l, T h, const F &f) {
  T r = -1, m;
  while (l <= h) {
    m = (l + h) / 2;
    if (f(m)) {
      l = m + 1;
      r = m;
    } else {
      h = m - 1;
    }
  }
  return r;
}
template <typename F>
double bshd(double l, double h, const F &f, double p = 1e-9) {
  unsigned int r = 3 + (unsigned int)log2((h - l) / p);
  while (r--) {
    double m = (l + h) / 2;
    if (f(m)) {
      l = m;
    } else {
      h = m;
    }
  }
  return (l + h) / 2;
}
template <typename T, typename F>
T bsl(T l, T h, const F &f) {
  T r = -1, m;
  while (l <= h) {
    m = (l + h) / 2;
    if (f(m)) {
      h = m - 1;
      r = m;
    } else {
      l = m + 1;
    }
  }
  return r;
}
template <typename F>
double bsld(double l, double h, const F &f, double p = 1e-9) {
  unsigned int r = 3 + (unsigned int)log2((h - l) / p);
  while (r--) {
    double m = (l + h) / 2;
    if (f(m)) {
      h = m;
    } else {
      l = m;
    }
  }
  return (l + h) / 2;
}
template <typename T>
T gcd(T a, T b) {
  if (a < b) swap(a, b);
  return b ? gcd(b, a % b) : a;
}
template <typename T>
class vector2 : public vector<vector<T>> {
 public:
  vector2() {}
  vector2(size_t a, size_t b, T t = T())
      : vector<vector<T>>(a, vector<T>(b, t)) {}
};
template <typename T>
class vector3 : public vector<vector2<T>> {
 public:
  vector3() {}
  vector3(size_t a, size_t b, size_t c, T t = T())
      : vector<vector2<T>>(a, vector2<T>(b, c, t)) {}
};
template <typename T>
class vector4 : public vector<vector3<T>> {
 public:
  vector4() {}
  vector4(size_t a, size_t b, size_t c, size_t d, T t = T())
      : vector<vector3<T>>(a, vector3<T>(b, c, d, t)) {}
};
template <typename T>
class vector5 : public vector<vector4<T>> {
 public:
  vector5() {}
  vector5(size_t a, size_t b, size_t c, size_t d, size_t e, T t = T())
      : vector<vector4<T>>(a, vector4<T>(b, c, d, e, t)) {}
};
struct TreeX {
  explicit TreeX(int N = 1) : N(N), M(0), logN(logceil(N)), _root(0), E(N) {}
  void addEdge(int u, int v) {
    ++M;
    E[u].push_back(v);
    E[v].push_back(u);
  }
  int la(int u, int depth) { return _la(u, depth); }
  inline int lca(int u, int v) { return _lca(u, v); }
  int parent(int u) { return P[u]; }
  void setRoot(int r) { _root = r; }
  int root() { return _root; }
  const vector<int> &neighbors(int u) const { return E[u]; }
  int depth(int u) const { return D[u]; }
  bool isAncestor(int top, int bottom) { return lca(top, bottom) == top; }
  bool sameBranch(int top, int bottom) {
    int l = lca(top, bottom);
    return l == top || l == bottom;
  }
  int _la(int u, int d) const {
    for (int i = 0; i < logN && u != -1; ++i) {
      if (d & (1 << i)) u = PP[i][u];
    }
    return u;
  }
  int _lca(int u, int v) {
    if (D[u] < D[v]) {
      swap(u, v);
    }
    u = _la(u, D[u] - D[v]);
    for (int i = logN - 1; i >= 0; --i)
      if (PP[i][u] != PP[i][v]) {
        u = PP[i][u];
        v = PP[i][v];
      }
    return u == v ? u : PP[0][v];
  }
  inline void calcParents() {
    assert(M == N - 1);
    if (P.size() == 0) {
      P.resize(N);
      D.resize(N);
      dfs(_root, -1, 0);
    }
  }
  void dfs(int u, int v, int d) {
    P[u] = v;
    D[u] = d;
    for (int w : E[u])
      if (v != w) dfs(w, u, d + 1);
  }
  inline void calcLA() {
    calcParents();
    if (PP.size() == 0) {
      PP = vector2<int>(logN, N, -1);
      for (int i = 0; i < N; ++i) {
        PP[0][i] = P[i];
      }
      for (int i = 1; i < logN; ++i)
        for (int j = 0; j < N; ++j)
          if (PP[i - 1][j] != -1) PP[i][j] = PP[i - 1][PP[i - 1][j]];
    }
  }
  int N, M, logN, _root;
  vector<vector<int>> E;
  vector<int> P, D;
  vector2<int> PP;
};
template <typename EdgeType>
class DFSOrder {
 public:
  DFSOrder(const vector<vector<EdgeType>> &_E)
      : T(0), N(_E.size()), E(_E), RevEnter(N), Enter(N), Exit(N) {
    dfs(0, -1);
  }
  vector<vector<EdgeType>> linearize() {
    vector<vector<EdgeType>> F(N);
    for (int i = 0; i < N; ++i) {
      for (auto v : E[i]) {
        F[conv(i)].push_back(conv(v));
      }
    }
    return F;
  }
  void dfs(int u, int p) {
    RevEnter[T] = u;
    Enter[u] = T++;
    for (auto v : E[u])
      if (t(v) != p) dfs(t(v), u);
    Exit[u] = T;
  }
  inline int t(const int &e) const { return e; }
  template <typename U>
  inline int t(const pair<int, U> &e) const {
    return e.first;
  }
  inline int conv(const int &e) const { return Enter[e]; }
  template <typename U>
  inline pair<int, U> conv(const pair<int, U> &e) const {
    return {Enter[e.first], e.second};
  }
  const vector<int> &revEnter() const { return RevEnter; }
  const vector<int> &enter() const { return Enter; }
  const vector<int> &exit() const { return Exit; }
  int T, N;
  const vector<vector<EdgeType>> &E;
  vector<int> Enter, Exit, RevEnter;
};
template <typename EdgeType>
class CentroidDecomposition {
 public:
  CentroidDecomposition(const vector<vector<EdgeType>> &E) : E(E) {}
  const vector<int> &findCentroids() {
    DFSOrder<EdgeType> DFS(E);
    auto EF = DFS.linearize();
    N = E.size();
    U.assign(N, -1);
    int L = 0;
    for (int j = 0; j < N;) {
      for (int i = N - 1; i >= 0; --i) {
        if (U[i] >= 0) continue;
        U[i] = -1;
        bool root = true;
        for (auto v : EF[i]) {
          if (U[t(v)] < 0) {
            if (t(v) > i)
              U[i] += U[t(v)];
            else
              root = false;
          }
        }
        if (root) {
          int n = -U[i], u = i, p = -1;
          while (true) {
            int s = n + U[u];
            for (auto v : EF[u])
              if (t(v) != p && U[t(v)] < 0) s = max(s, -U[t(v)]);
            if (2 * s <= n) {
              U[u] = j++;
              break;
            } else {
              for (auto v : EF[u])
                if (t(v) != p && -U[t(v)] > n / 2) {
                  p = u;
                  u = t(v);
                  break;
                }
            }
          }
        }
      }
    }
    vector<int> Ans(N);
    for (int i = 0; i < N; ++i) Ans[i] = U[DFS.enter()[i]];
    swap(Ans, U);
    return U;
  }
  inline int t(const int &e) const { return e; }
  template <typename U>
  inline int t(const pair<int, U> &e) const {
    return e.first;
  }
  int N;
  const vector<vector<EdgeType>> &E;
  vector<int> U;
};
struct Bipartite {
  explicit Bipartite(unsigned int A, unsigned int B)
      : A(A), B(B), N(A + B), ms(-1), H(N, -1), used(A) {}
  void addEdge(int u, int v) {
    G.push_back(v);
    P.push_back(H[u]);
    H[u] = (unsigned int)G.size() - 1;
  }
  unsigned int matchingSize() {
    calcMatching();
    return ms;
  }
  int matched(int v) {
    calcMatching();
    return M[v];
  }
  vector<int> cover() {
    calcCover();
    vector<int> C;
    for (int i = 0; i < N; ++i) {
      if (Z[i] != (i < A)) C.push_back(i);
    }
    return C;
  }
  vector<int> indep() {
    calcCover();
    vector<int> I;
    for (int i = 0; i < N; ++i) {
      if (Z[i] == (i < A)) I.push_back(i);
    }
    return I;
  }
  void konigDfs(int u) {
    if (Z[u]) {
      return;
    }
    Z[u] = true;
    if (u < A) {
      for (unsigned int p = H[u]; p != -1; p = P[p]) {
        unsigned int v = G[p];
        if (v != M[u]) konigDfs(v);
      }
    } else if (M[u] != -1)
      konigDfs(M[u]);
  }
  bool matchingDfs(int u) {
    if (used[u]) return false;
    used[u] = true;
    for (unsigned int p = H[u]; p != -1; p = P[p]) {
      unsigned int v = G[p];
      if (M[v] == -1) {
        M[u] = v;
        M[v] = u;
        ++ms;
        return true;
      }
    }
    for (unsigned int p = H[u]; p != -1; p = P[p]) {
      unsigned int v = G[p];
      if (matchingDfs(M[v])) {
        M[u] = v;
        M[v] = u;
        return true;
      }
    }
    return false;
  }
  inline void calcMatching() {
    if (ms != -1) {
      return;
    }
    M = vector<unsigned int>(N, -1);
    size_t cur;
    ms = 0;
    do {
      cur = ms;
      for (int i = 0; i < A; ++i) used[i] = false;
      for (int i = 0; i < A; ++i)
        if (M[i] == -1) matchingDfs(i);
    } while (cur != ms);
  }
  inline void calcCover() {
    if (Z.size() == N) {
      return;
    }
    calcMatching();
    Z = vector<bool>(N, false);
    for (int i = 0; i < A; ++i)
      if (M[i] == -1) konigDfs(i);
  }
  unsigned int N, A, B, ms;
  vector<unsigned int> M, H, G, P;
  vector<bool> Z, used;
};
struct DirectedGraph {
  explicit DirectedGraph(int N) : N(N), E(N) {}
  void addEdge(int u, int v) { E[u].push_back({v}); }
  int stronglyConnectedComponent(int v) {
    calcStronglyConnectedComponents();
    return SCC[v];
  }
  bool stronglyConnected(int u, int v) {
    calcStronglyConnectedComponents();
    return SCC[u] == SCC[v];
  }
  const vector<int> &stronglyConnectedPermutation() {
    calcStronglyConnectedComponents();
    return O;
  }
  inline void calcReverseEdges() {
    if (ER.size() == N) {
      return;
    }
    ER.resize(N);
    for (int i = 0; i < N; ++i)
      for (int u : E[i]) ER[u].push_back(i);
  }
  inline void calcStronglyConnectedComponents() {
    if (SCC.size() == N) {
      return;
    }
    SCC.resize(N);
    O.resize(N);
    calcReverseEdges();
    vector<bool> V(N, false);
    vector<int> F(N, 0);
    int t = 0;
    for (int i = N - 1; i >= 0; i--) {
      if (!V[i]) {
        dfsReverse(i, V, F, t);
      }
      O[N - 1 - F[i]] = i;
    }
    fill(V.begin(), V.end(), false);
    for (int i = 0; i < N; i++) {
      if (!V[O[i]]) dfsForward(O[i], O[i], V);
    }
  }
  void dfsForward(int i, int p, vector<bool> &V) {
    V[i] = true;
    SCC[i] = p;
    for (int v : E[i])
      if (!V[v]) dfsForward(v, p, V);
  }
  void dfsReverse(int i, vector<bool> &V, vector<int> &F, int &t) {
    V[i] = true;
    for (int v : ER[i]) {
      if (!V[v]) dfsReverse(v, V, F, t);
    }
    F[i] = t++;
  }
  int N;
  vector<vector<int>> E, ER;
  vector<int> SCC, O;
};
struct TwoSat {
  int N;
  vector<int> val;
  vector<char> valid;
  vector<vector<int>> G;
  TwoSat(int N) : N(N), val(2 * N), G(2 * N) {}
  void addImplication(int a, bool w, int b, bool first) {
    G[2 * a + w].push_back(2 * b + first);
  }
  void addOr(int a, bool w, int b, bool first) {
    addImplication(a, !w, b, first);
    addImplication(b, !first, a, w);
  }
  void addTrue(int first) { addImplication(first, false, first, true); }
  void addFalse(int first) { addImplication(first, true, first, false); }
  int time() { return valid.size() - 1; }
  bool dfs(int first) {
    if (valid[abs(val[first])]) return val[first] > 0;
    val[first] = time();
    val[first ^ 1] = -time();
    for (int e : G[first])
      if (!dfs(e)) return false;
    return true;
  }
  bool value(int i) const { return val[2 * i] < 0; }
  bool solve() {
    fill(val.begin(), val.end(), 0);
    valid.assign(1, 0);
    for (int i = 0; i < val.size(); i += 2) {
      if (!valid[abs(val[i])]) {
        valid.push_back(1);
        if (!dfs(i)) {
          valid.back() = 0;
          valid.push_back(1);
          if (!dfs(i + 1)) return false;
        }
      }
    }
    return true;
  }
};
class DRecoverAFunctionalGraph {
 public:
  void solve(istream &cin, ostream &cout) {
    int N;
    cin >> N;
    vector<std::pair<int, int>> V(N);
    vector2<vector<int>> Full(N + 1, N + 1);
    vector<vector<int>> Cycle(N + 1);
    vector<vector<int>> Precycle(N + 1);
    vector<bool> HasCycle(N + 1, false);
    vector<int> Free;
    vector<std::pair<int, int>> Need;
    for (int i = 0; i < N; ++i) {
      string s;
      int a;
      cin >> s;
      if (s == "?")
        V[i].first = -1;
      else {
        stringstream ss(s);
        ss >> a;
        V[i].first = a;
      }
      cin >> s;
      if (s == "?")
        V[i].second = -1;
      else {
        stringstream ss(s);
        ss >> a;
        V[i].second = a;
      }
      if (V[i].first == -1) {
        if (V[i].second == -1) {
          Free.push_back(i);
        } else {
          HasCycle[V[i].second] = true;
          Cycle[V[i].second].push_back(i);
        }
      } else {
        if (V[i].second == -1) {
          Precycle[V[i].first].push_back(i);
        } else {
          HasCycle[V[i].second] = true;
          Full[V[i].second][V[i].first].push_back(i);
        }
      }
    }
    for (int cyc = 1; cyc <= N; ++cyc) {
      bool has = false;
      for (int prec = N; prec > 0; --prec) {
        if (!Full[cyc][prec].empty()) {
          has = true;
        } else if (has) {
          Need.emplace_back(prec, cyc);
        }
      }
      if (has || !Cycle[cyc].empty() || !Full[cyc][0].empty()) {
        int first = Full[cyc][0].size();
        while (first == 0 || first % cyc != 0) {
          first++;
          Need.emplace_back(0, cyc);
        }
      }
    }
    int highestPrec = -1;
    for (int prec = N; prec > 0; --prec) {
      if (!Precycle[prec].empty()) {
        highestPrec = max(highestPrec, prec);
      }
    }
    for (int cyc = 1; cyc <= N; ++cyc) {
      vector<std::pair<int, int>> Real = Need;
      for (int prec = N; prec >= 0; --prec) {
        if (!Full[cyc][prec].empty()) break;
        if (prec <= highestPrec) {
          if (prec == 0) {
            if (!HasCycle[cyc]) {
              for (int j = 0; j < cyc; ++j) {
                Real.emplace_back(0, cyc);
              }
            }
          } else {
            Real.emplace_back(prec, cyc);
          }
        }
      }
      Bipartite G(N, Real.size());
      for (int i = 0; i < N; ++i) {
        for (int j = 0; j < Real.size(); ++j) {
          if ((V[i].first == -1 || V[i].first == Real[j].first) &&
              (V[i].second == -1 || V[i].second == Real[j].second) &&
              (V[i].first == -1 || V[i].second == -1)) {
            G.addEdge(i, N + j);
          }
        }
      }
      G.calcMatching();
      if (G.matchingSize() == Real.size()) {
        auto W = V;
        for (int i = 0; i < N; ++i) {
          if (G.matched(i) != -1) {
            W[i] = Real[G.matched(i) - N];
          } else if (W[i] == std::pair<int, int>{-1, -1}) {
            W[i] = {0, 1};
          } else if (W[i].first == -1) {
            W[i].first = 1;
          } else if (W[i].second == -1) {
            if (W[i].first == 0) {
              W[i].second = 1;
            } else {
              W[i].second = cyc;
            }
          }
        }
        vector<int> Par(N, -1);
        vector<vector<int>> Q(N + 1);
        for (int i = 0; i < N; ++i) {
          if (W[i].first > 0) {
            for (int j = 0; j < N; ++j) {
              if (W[j].first + 1 == W[i].first && W[j].second == W[i].second)
                Par[i] = j;
            }
          } else {
            Q[W[i].second].push_back(i);
          }
        }
        for (int i = 1; i <= N; ++i) {
          for (int j = 0; j < Q[i].size(); ++j) {
            Par[Q[i][j]] = j % i == 0 ? Q[i][j + i - 1] : Q[i][j - 1];
          }
        }
        for (int &p : Par) ++p;
        cout << Par;
        return;
      }
    }
    cout << -1 << endl;
  }
};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  DRecoverAFunctionalGraph solver;
  std::istream &in(std::cin);
  std::ostream &out(std::cout);
  solver.solve(in, out);
  return 0;
}