Problem: You are given positions (X_i, Y_i) of N enemy rooks on an infinite chessboard. No two rooks attack each other (at most one rook per row or column).

You're going to replace one rook with a king and then move the king repeatedly to beat as many rooks as possible.

You can't enter a cell that is being attacked by a rook. Additionally, you can't move diagonally to an empty cell (but you can beat a rook diagonally).

(So this king moves like a superpawn that beats diagonally in 4 directions and moves horizontally/vertically in 4 directions.)

For each rook, consider replacing it with a king, and find the minimum possible number of moves needed to beat the maximum possible number of rooks.

Constraints

* 2 \leq N \leq 200\,000
* 1 \leq X_i, Y_i \leq 10^6
* X_i \neq X_j
* Y_i \neq Y_j
* All values in input are integers.

Input

Input is given from Standard Input in the following format.


N
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N


Output

Print N lines. The i-th line is for scenario of replacing the rook at (X_i, Y_i) with your king. This line should contain one integer: the minimum number of moves to beat M_i rooks where M_i denotes the maximum possible number of beaten rooks in this scenario (in infinite time).

Examples

Input

6
1 8
6 10
2 7
4 4
9 3
5 1


Output

5
0
7
5
0
0


Input

5
5 5
100 100
70 20
81 70
800 1


Output

985
985
1065
1034
0


Input

10
2 5
4 4
13 12
12 13
14 17
17 19
22 22
16 18
19 27
25 26


Output

2
2
9
9
3
3
24
5
0
25

Solution (in CPP):

Solution:
#include <bits/stdc++.h>

using namespace std;

template <typename T>
void debug_out(T t) {
  cerr << t;
}

template <typename A, typename B>
void debug_out(pair<A, B> u) {
  cerr << "(" << u.first << " " << u.second << ")";
}

template <typename T>
void debug_out(vector<T> t) {
  int sz = t.size();
  for(int i = 0; i < sz; i++) {
    debug_out(t[i]);
    if(i != sz - 1) cerr << ", ";
  }
}

template <typename T>
void debug_out(vector<vector<T>> t) {
  int sz = t.size();
  for(int i = 0; i < sz; i++) {
    debug_out(t[i]);
    if(i != sz - 1) cerr << endl;
  }
}

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  debug_out(H);
  cerr << " ";
  debug_out(T...);
}

template <typename T>
void debug_out(set<T> a) {
  vector<T> _a;
  for(T t : a) _a.push_back(t);
  debug_out(_a);
}

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:" << endl, debug_out(__VA_ARGS__), cerr << endl;

template <typename T, class F = function<T(const T&, const T&)>>
class SparseTable {
 public:
  int n;
  vector<vector<T>> mat;
  F func;

  SparseTable(const vector<T>& a, const F& f) : func(f) {
    n = static_cast<int>(a.size());
    int max_log = 32 - __builtin_clz(n);
    mat.resize(max_log);
    mat[0] = a;
    for (int j = 1; j < max_log; j++) {
      mat[j].resize(n - (1 << j) + 1);
      for (int i = 0; i <= n - (1 << j); i++) {
        mat[j][i] = func(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]);
      }
    }
  }

  T get(int from, int to) const {
    assert(0 <= from && from <= to && to <= n - 1);
    int lg = 32 - __builtin_clz(to - from + 1) - 1;
    return func(mat[lg][from], mat[lg][to - (1 << lg) + 1]);
  }
};

int n;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  vector<pair<int, int>> rooks(n);
  for(int i = 0; i < n; i++) cin >> rooks[i].first >> rooks[i].second;
  vector<int> final_id(n);
  iota(final_id.begin(), final_id.end(), 0);
  sort(final_id.begin(), final_id.end(), [&](int i, int j){return rooks[i] < rooks[j];});
  sort(rooks.begin(), rooks.end());
  vector<int> to_sort(n);
  iota(to_sort.begin(), to_sort.end(), 0);
  sort(to_sort.begin(), to_sort.end(), [&](int i, int j){return rooks[i].second < rooks[j].second;});
  vector<int> pos(n);
  for(int i = 0; i < n; i++) pos[to_sort[i]] = i;
  SparseTable<int> to_min(pos, [&](int i, int j){return min(i, j);});
  SparseTable<int> to_max(pos, [&](int i, int j){return max(i, j);});
  vector<int> go_left(n);
  vector<int> go_right(n);
  for(int i = 0; i < n; i++) {
    if(i == 0) continue;
    if(abs(pos[i] - pos[i - 1]) == 1) go_left[i] = go_left[i - 1];
    else go_left[i] = i;
  }
  for(int i = n - 1; i >= 0; i--) {
    if(i == n - 1) {
      go_right[i] = n - 1;
      continue;
    }
    if(abs(pos[i] - pos[i + 1]) == 1) go_right[i] = go_right[i + 1];
    else go_right[i] = i;
  }
  map<pair<int, int>, pair<long long, long long>> dp;
  map<pair<int, int>, int> cursed;
  auto dis = [&](int i, int j) {
    return 1LL * abs(rooks[i].first - rooks[j].first) + 1LL * abs(rooks[i].second - rooks[j].second);
  };
  function<pair<long long, long long>(int, int)> dfs = [&](int l, int r) {
    if(dp.count(make_pair(l, r))) return dp[make_pair(l, r)];
    int sl = l;
    int sr = r;
    if(l) {
      int v = pos[l - 1];
      int x = to_min.get(l, r);
      int y = to_max.get(l, r);
      if(abs(v - x) == 1 || abs(v - y) == 1) {
        sl = go_left[l - 1];
      }
    }
    if(r < n - 1) {
      int v = pos[r + 1];
      int x = to_min.get(l, r);
      int y = to_max.get(l, r);
      if(abs(v - x) == 1 || abs(v - y) == 1) {
        sr = go_right[r + 1];
      }
    }
    if(sl == l && sr == r) {
      cursed[make_pair(l, r)] = r - l + 1;
      return make_pair(0LL, 0LL);
    }
    auto foo = dfs(sl, sr);
    cursed[make_pair(l, r)] = cursed[make_pair(sl, sr)];
    pair<long long, long long> res = foo;
    long long get_left = res.first;
    long long get_right = res.second;
    if(sl == l && sr != r) {
      dp[make_pair(l, r)] = make_pair(dis(l, sr) + get_right, dis(r, sr) + get_right);
    }
    if(sl != l && sr == r) {
      dp[make_pair(l, r)] = make_pair(dis(l, sl) + get_left, dis(r, sl) + get_left);
    }
    if(sl != l && sr != r) {
      long long move_left = min(dis(l, sr) + dis(sr, sl) + res.first, dis(l, sl) + dis(sl, sr) + res.second);
      long long move_right = min(dis(r, sr) + dis(sr, sl) + res.first, dis(r, sl) + dis(sl, sr) + res.second);
      dp[make_pair(l, r)] = make_pair(move_left, move_right);
    }
    return dp[make_pair(l, r)];
  };
  vector<long long> res(n);
  for(int i = 0; i < n; i++) {
    auto foo = dfs(go_left[i], go_right[i]);
    int cnt = cursed[make_pair(go_left[i], go_right[i])];
    pair<long long, long long> way = foo;
    res[final_id[i]] = min(dis(i, go_left[i]) + dis(go_left[i], go_right[i]) + way.second, dis(i, go_right[i]) + dis(go_right[i], go_left[i]) + way.first) - cnt + 1;
  }
  for(long long i : res) {
    cout << i << "\n";
  }
  return 0;
}