/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <iostream>
#include <fstream>

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

#define pb push_back
#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second

using namespace std;

typedef long long int64;
typedef vector<int> vi;

struct node{
  int s,e,m;
  ll val=0,lazy=0;
  node *l,*r;

  node (int _s,int _e){
    s=_s,e=_e,m=s+e>>1;

    if (s!=e){
      l=new node(s,m);
      r=new node(m+1,e);
    }
  }

  void propo(){
    if (lazy){
      val+=lazy;
      if (s!=e){
        l->lazy+=lazy;
        r->lazy+=lazy;
      }
      lazy=0;
    }
  }

  void update(int i,int j,ll k){
    if (s==i && e==j) lazy+=k;
    else{
      if (j<=m) l->update(i,j,k);
      else if (m<i) r->update(i,j,k);
      else l->update(i,m,k),r->update(m+1,j,k);

      l->propo(),r->propo();
      val=min(l->val,r->val);
    }
  }

  ll query(int i,int j){
    propo();

    if (s==i && e==j) return val;
    else if (j<=m) return l->query(i,j);
    else if (m<i) return r->query(i,j);
    else return min(l->query(i,m),r->query(m+1,j));
  }
};

int n,q;
int arr[200005];
ii range[400005];
ii span[400005];
vector<int> children[400005];
int parent[400005];
int typ[400005];
int idx; //new index to assign to nodes

ii get_range(ii i,ii j){
  return ii(min(i.fi,j.fi),max(i.se,j.se));
}

void add_edge(int u,int v){ //u is parent of v
  parent[v]=u;
  children[u].push_back(v);
}

bool adj(int i,int j){
  return range[i].se==range[j].fi-1;
}

int length(int i){
  return range[i].se-range[i].fi+1;
}

int build(){
  idx=n;
  memset(parent,-1,sizeof(parent));

  node *root=new node(0,200005);
  vector<int> mx={-1},mn={-1}; //stacks for max and min

  vector<int> nodes; //stack of cut and join nodes

  rep(x,0,n){
    //update Q values
    while (mx.back()!=-1 && arr[mx.back()]<arr[x]){
      int temp=mx.back();
      mx.pop_back();
      root->update(mx.back()+1,temp,arr[x]-arr[temp]);
    }
    mx.push_back(x);

    while (mn.back()!=-1 && arr[mn.back()]>arr[x]){
      int temp=mn.back();
      mn.pop_back();
      root->update(mn.back()+1,temp,arr[temp]-arr[x]);
    }
    mn.push_back(x);

    //handle stack updates
    range[x]=ii(arr[x],arr[x]);
    span[x]=ii(x,x);
    int curr=x;

    while (true){
      if (!nodes.empty() && (adj(nodes.back(),curr) || adj(curr,nodes.back()))){
        if ((adj(nodes.back(),curr) && typ[nodes.back()]==1)||
            (adj(curr,nodes.back()) && typ[nodes.back()]==2)){
          add_edge(nodes.back(),curr);

          range[nodes.back()]=get_range(range[nodes.back()],range[curr]);
          span[nodes.back()]=get_range(span[nodes.back()],span[curr]);

          curr=nodes.back();
          nodes.pop_back();
        }
        else{ //make a new join node
          typ[idx]=(adj(nodes.back(),curr) ? 1:2);
          add_edge(idx,nodes.back());
          add_edge(idx,curr);

          range[idx]=get_range(range[nodes.back()],range[curr]);
          span[idx]=get_range(span[nodes.back()],span[curr]);

          nodes.pop_back();
          curr=idx++;
        }
      }
      else if (x-(length(curr)-1) && root->query(0,x-length(curr))==0){
        int len=length(curr);
        ii r=range[curr];
        ii s=span[curr];

        add_edge(idx,curr);

        do{
          len+=length(nodes.back());
          r=get_range(r,range[nodes.back()]);
          s=get_range(s,span[nodes.back()]);

          add_edge(idx,nodes.back());

          nodes.pop_back();
        } while (r.se-r.fi+1!=len);

        reverse(all(children[idx]));
        range[idx]=r;
        span[idx]=s;
        curr=idx++;
      }
      else{
        break;
      }
    }

    nodes.push_back(curr);
    root->update(0,x,-1);
  }

  assert(nodes.size() == 1);
  return nodes[0];
}

constexpr int64 INF = (int64) 1e18;


class Task {
 public:
  vector<int> compress(const vector<int64>& x) {
    vector<int64> xs = x;
    sort(all(xs));
    vector<int> res(x.size());
    for (int i = 0; i < x.size(); ++i) {
      res[i] = lower_bound(all(xs), x[i]) - xs.begin();
    }
    return res;
  }

  void dfs(int root, int64 extraIfMin, int64 extraIfMax) {
    if (range[root].first == range[root].second) {
      answers[answerPos[range[root].first]] = min(extraIfMin, extraIfMax);
      return;
    }
    if (typ[root] == 0) {
      for (int x : children[root]) {
        dfs(x, 0, 0);
      }
    } else {
      vector<int> nextNon1(children[root].size() + 1);
      nextNon1[children[root].size()] = children[root].size();
      for (int i = children[root].size() - 1; i >= 0; --i) {
        if (range[children[root][i]].first == range[children[root][i]].second) {
          nextNon1[i] = nextNon1[i + 1];
        } else {
          nextNon1[i] = i;
        }
      }
      int prevNon1 = -1;
      for (int i = 0; i < children[root].size(); ++i) {
        int j = prevNon1 + 1;
        int k = nextNon1[i + 1] - 1;
        int i1 = range[children[root][i]].first;
        int i2 = range[children[root][i]].second;
        if (i1 != i2) {
          prevNon1 = i;
        }
        int j1 = min(range[children[root][j]].first, range[children[root][k]].first);
        int j2 = max(range[children[root][j]].second, range[children[root][k]].second);
        int64 emin = INF;
        int64 emax = INF;
        for (int inner = 0; inner < 2; ++inner) {
          int64 val = 0;
          int from = inner == 0 ? i1 : i2;
          if (j1 < i1) {
            val += abs(x[answerPos[from]] - x[answerPos[j1]]) + abs(y[answerPos[from]] - y[answerPos[j1]]);
            val += abs(x[answerPos[j2]] - x[answerPos[j1]]) + abs(y[answerPos[j2]] - y[answerPos[j1]]);
          } else {
            val += abs(x[answerPos[from]] - x[answerPos[j2]]) + abs(y[answerPos[from]] - y[answerPos[j2]]);
          }
          if (j == 0 && k + 1 == children[root].size()) {
            val += extraIfMax;
          }
          if (inner == 0) {
            emin = min(emin, val);
          } else {
            emax = min(emax, val);
          }
          val = 0;
          if (j2 > i2) {
            val += abs(x[answerPos[from]] - x[answerPos[j2]]) + abs(y[answerPos[from]] - y[answerPos[j2]]);
            val += abs(x[answerPos[j2]] - x[answerPos[j1]]) + abs(y[answerPos[j2]] - y[answerPos[j1]]);
          } else {
            val += abs(x[answerPos[from]] - x[answerPos[j1]]) + abs(y[answerPos[from]] - y[answerPos[j1]]);
          }
          if (j == 0 && k == children[root].size() - 1) {
            val += extraIfMin;
          }
          if (inner == 0) {
            emin = min(emin, val);
          } else {
            emax = min(emax, val);
          }
        }
        emin -= (k - j);
        emax -= (k - j);
        dfs(children[root][i], emin, emax);
      }
    }
  }

  vector<int64> x;
  vector<int64> y;
  vector<int64> answers;
  vector<int> answerPos;

  void solveOne(istream &in, ostream &out) {
    in >> n;
    x = vector<int64>(n);
    y = vector<int64>(n);
    for (int i = 0; i < n; ++i) {
      in >> x[i] >> y[i];
    }
    vector<int> xc = compress(x);
    vector<int> yc = compress(y);
    answers = vector<int64>(n);
    answerPos = vector<int>(n);
    for (int i = 0; i < n; ++i) {
      arr[xc[i]] = yc[i];
      answerPos[yc[i]] = i;
    }
    int root = build();
    dfs(root, 0, 0);
    for (auto x : answers) {
      out << x << "\n";
    }
  }

  void solve(std::istream &in, std::ostream &out) {
    int nt = 1;
    for (int it = 0; it < nt; ++it) {
      solveOne(in, out);
    }
  }
};


int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  Task solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  solver.solve(in, out);
  return 0;
}

### Prompt

Create a solution in CPP for the following 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

### Response

```cpp
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <iostream>
#include <fstream>

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

#define pb push_back
#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second

using namespace std;

typedef long long int64;
typedef vector<int> vi;

struct node{
  int s,e,m;
  ll val=0,lazy=0;
  node *l,*r;

  node (int _s,int _e){
    s=_s,e=_e,m=s+e>>1;

    if (s!=e){
      l=new node(s,m);
      r=new node(m+1,e);
    }
  }

  void propo(){
    if (lazy){
      val+=lazy;
      if (s!=e){
        l->lazy+=lazy;
        r->lazy+=lazy;
      }
      lazy=0;
    }
  }

  void update(int i,int j,ll k){
    if (s==i && e==j) lazy+=k;
    else{
      if (j<=m) l->update(i,j,k);
      else if (m<i) r->update(i,j,k);
      else l->update(i,m,k),r->update(m+1,j,k);

      l->propo(),r->propo();
      val=min(l->val,r->val);
    }
  }

  ll query(int i,int j){
    propo();

    if (s==i && e==j) return val;
    else if (j<=m) return l->query(i,j);
    else if (m<i) return r->query(i,j);
    else return min(l->query(i,m),r->query(m+1,j));
  }
};

int n,q;
int arr[200005];
ii range[400005];
ii span[400005];
vector<int> children[400005];
int parent[400005];
int typ[400005];
int idx; //new index to assign to nodes

ii get_range(ii i,ii j){
  return ii(min(i.fi,j.fi),max(i.se,j.se));
}

void add_edge(int u,int v){ //u is parent of v
  parent[v]=u;
  children[u].push_back(v);
}

bool adj(int i,int j){
  return range[i].se==range[j].fi-1;
}

int length(int i){
  return range[i].se-range[i].fi+1;
}

int build(){
  idx=n;
  memset(parent,-1,sizeof(parent));

  node *root=new node(0,200005);
  vector<int> mx={-1},mn={-1}; //stacks for max and min

  vector<int> nodes; //stack of cut and join nodes

  rep(x,0,n){
    //update Q values
    while (mx.back()!=-1 && arr[mx.back()]<arr[x]){
      int temp=mx.back();
      mx.pop_back();
      root->update(mx.back()+1,temp,arr[x]-arr[temp]);
    }
    mx.push_back(x);

    while (mn.back()!=-1 && arr[mn.back()]>arr[x]){
      int temp=mn.back();
      mn.pop_back();
      root->update(mn.back()+1,temp,arr[temp]-arr[x]);
    }
    mn.push_back(x);

    //handle stack updates
    range[x]=ii(arr[x],arr[x]);
    span[x]=ii(x,x);
    int curr=x;

    while (true){
      if (!nodes.empty() && (adj(nodes.back(),curr) || adj(curr,nodes.back()))){
        if ((adj(nodes.back(),curr) && typ[nodes.back()]==1)||
            (adj(curr,nodes.back()) && typ[nodes.back()]==2)){
          add_edge(nodes.back(),curr);

          range[nodes.back()]=get_range(range[nodes.back()],range[curr]);
          span[nodes.back()]=get_range(span[nodes.back()],span[curr]);

          curr=nodes.back();
          nodes.pop_back();
        }
        else{ //make a new join node
          typ[idx]=(adj(nodes.back(),curr) ? 1:2);
          add_edge(idx,nodes.back());
          add_edge(idx,curr);

          range[idx]=get_range(range[nodes.back()],range[curr]);
          span[idx]=get_range(span[nodes.back()],span[curr]);

          nodes.pop_back();
          curr=idx++;
        }
      }
      else if (x-(length(curr)-1) && root->query(0,x-length(curr))==0){
        int len=length(curr);
        ii r=range[curr];
        ii s=span[curr];

        add_edge(idx,curr);

        do{
          len+=length(nodes.back());
          r=get_range(r,range[nodes.back()]);
          s=get_range(s,span[nodes.back()]);

          add_edge(idx,nodes.back());

          nodes.pop_back();
        } while (r.se-r.fi+1!=len);

        reverse(all(children[idx]));
        range[idx]=r;
        span[idx]=s;
        curr=idx++;
      }
      else{
        break;
      }
    }

    nodes.push_back(curr);
    root->update(0,x,-1);
  }

  assert(nodes.size() == 1);
  return nodes[0];
}

constexpr int64 INF = (int64) 1e18;


class Task {
 public:
  vector<int> compress(const vector<int64>& x) {
    vector<int64> xs = x;
    sort(all(xs));
    vector<int> res(x.size());
    for (int i = 0; i < x.size(); ++i) {
      res[i] = lower_bound(all(xs), x[i]) - xs.begin();
    }
    return res;
  }

  void dfs(int root, int64 extraIfMin, int64 extraIfMax) {
    if (range[root].first == range[root].second) {
      answers[answerPos[range[root].first]] = min(extraIfMin, extraIfMax);
      return;
    }
    if (typ[root] == 0) {
      for (int x : children[root]) {
        dfs(x, 0, 0);
      }
    } else {
      vector<int> nextNon1(children[root].size() + 1);
      nextNon1[children[root].size()] = children[root].size();
      for (int i = children[root].size() - 1; i >= 0; --i) {
        if (range[children[root][i]].first == range[children[root][i]].second) {
          nextNon1[i] = nextNon1[i + 1];
        } else {
          nextNon1[i] = i;
        }
      }
      int prevNon1 = -1;
      for (int i = 0; i < children[root].size(); ++i) {
        int j = prevNon1 + 1;
        int k = nextNon1[i + 1] - 1;
        int i1 = range[children[root][i]].first;
        int i2 = range[children[root][i]].second;
        if (i1 != i2) {
          prevNon1 = i;
        }
        int j1 = min(range[children[root][j]].first, range[children[root][k]].first);
        int j2 = max(range[children[root][j]].second, range[children[root][k]].second);
        int64 emin = INF;
        int64 emax = INF;
        for (int inner = 0; inner < 2; ++inner) {
          int64 val = 0;
          int from = inner == 0 ? i1 : i2;
          if (j1 < i1) {
            val += abs(x[answerPos[from]] - x[answerPos[j1]]) + abs(y[answerPos[from]] - y[answerPos[j1]]);
            val += abs(x[answerPos[j2]] - x[answerPos[j1]]) + abs(y[answerPos[j2]] - y[answerPos[j1]]);
          } else {
            val += abs(x[answerPos[from]] - x[answerPos[j2]]) + abs(y[answerPos[from]] - y[answerPos[j2]]);
          }
          if (j == 0 && k + 1 == children[root].size()) {
            val += extraIfMax;
          }
          if (inner == 0) {
            emin = min(emin, val);
          } else {
            emax = min(emax, val);
          }
          val = 0;
          if (j2 > i2) {
            val += abs(x[answerPos[from]] - x[answerPos[j2]]) + abs(y[answerPos[from]] - y[answerPos[j2]]);
            val += abs(x[answerPos[j2]] - x[answerPos[j1]]) + abs(y[answerPos[j2]] - y[answerPos[j1]]);
          } else {
            val += abs(x[answerPos[from]] - x[answerPos[j1]]) + abs(y[answerPos[from]] - y[answerPos[j1]]);
          }
          if (j == 0 && k == children[root].size() - 1) {
            val += extraIfMin;
          }
          if (inner == 0) {
            emin = min(emin, val);
          } else {
            emax = min(emax, val);
          }
        }
        emin -= (k - j);
        emax -= (k - j);
        dfs(children[root][i], emin, emax);
      }
    }
  }

  vector<int64> x;
  vector<int64> y;
  vector<int64> answers;
  vector<int> answerPos;

  void solveOne(istream &in, ostream &out) {
    in >> n;
    x = vector<int64>(n);
    y = vector<int64>(n);
    for (int i = 0; i < n; ++i) {
      in >> x[i] >> y[i];
    }
    vector<int> xc = compress(x);
    vector<int> yc = compress(y);
    answers = vector<int64>(n);
    answerPos = vector<int>(n);
    for (int i = 0; i < n; ++i) {
      arr[xc[i]] = yc[i];
      answerPos[yc[i]] = i;
    }
    int root = build();
    dfs(root, 0, 0);
    for (auto x : answers) {
      out << x << "\n";
    }
  }

  void solve(std::istream &in, std::ostream &out) {
    int nt = 1;
    for (int it = 0; it < nt; ++it) {
      solveOne(in, out);
    }
  }
};


int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  Task solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  solver.solve(in, out);
  return 0;
}

```