#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(lmao) lmao.begin(), lmao.end()

using namespace std;

typedef pair<int,int> pii;
typedef tuple<int,int,int> tp;
const int N = 1e6 + 5;
const int oo = 2e9;

int n, m, s;
vector<pii> vr[N];
vector<int> f[N], p[N];
priority_queue<tp, vector<tp>, greater<tp>> pq;

void update(int u,int v,int w){
  if(f[u][v] <= w) return;
  pq.push({f[u][v] = w, u, v});
}

void pro(int w,int u,int v){
  int bf = (u == 1 ? n : u - 1), nx = (u == n ? 1 : u + 1);
  int nb = lower_bound(all(p[bf]), v) - p[bf].begin(),
  nt = lower_bound(all(p[nx]), v) - p[nx].begin();
  nb -= (vr[bf][nb].se != 2);
  update(bf, nb, w + 1);
  nt -= (vr[nx][nt].se != 2);
  update(nx, nt, w + 1);
}

set<int> g[N], h[N];

int dis(int u){
  return min(abs(u - s), abs(u - n) + s);
}

signed main(){
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define task "v"
  if(fopen(task ".inp","r")){
    freopen(task ".inp","r",stdin);
    freopen(task ".out","w",stdout);
  }
  cin >> n >> m >> s;
  for(int i = 1; i <= m; i ++){
    int d, t; cin >> d >> t;
    int nxt = (t == n ? 1 : t + 1);
    vr[nxt].pb({d, 0});
    vr[t].pb({d, 1});
    p[nxt].pb(d);
    p[t].pb(d);
  }
  for(int i = 1; i <= n; i ++){
    p[i].pb(0);
    vr[i].pb({0, 2});
  }
  for(int i = 1; i <= n; i ++){
    int bf = (i == 1 ? n : i - 1), nt = (i == n ? 1 : i + 1);
    for(auto j : p[bf]) g[i].insert(j);
    for(auto j : p[nt]) g[i].insert(j);
    for(auto j : p[i]) h[i].insert(j);
  }
  for(int i = 1; i <= n; i ++){
    for(auto j : g[i]) if(h[i].find(j) == h[i].end())
      p[i].pb(j), vr[i].pb({j, 2});

    sort(all(p[i]));
    sort(all(vr[i]));
    for(auto j : p[i]){
      f[i].pb(oo);
      f[i].pb(oo);
    }
  }

  int ans = oo;
  pq.push({f[s][vr[s].size() - 1] = 0, s, vr[s].size() - 1});
  for(int i = 1; i <= n; i ++) if(i != s){
    pq.push({f[i][vr[i].size() - 1] = dis(i), i, vr[i].size() - 1});
  }
  while(!pq.empty()){
    int w, u, v; tie(w, u, v) = pq.top(); pq.pop();
    if(w > f[u][v]) continue;
//    cerr << w << " " << u << " " << v << " y\n";
    int bf = (u == 1 ? n : u - 1), nx = (u == n ? 1 : u + 1);
    if(!v){
      update(bf, 0, w + 1);
      update(nx, 0, w + 1);
      continue;
    }


    if(vr[u][v].se == 2){
      pro(w, u, vr[u][v].fi + 1);
      pro(w, u, vr[u][v].fi);
      update(u, v - 1, w);
      continue;
    }


    pro(w, u, vr[u][v].fi + 1);
    if(vr[u][v].se){
      int k = lower_bound(all(p[nx]), p[u][v]) - p[nx].begin();
      update(nx, k - 1, w);
    }else{
      int k = lower_bound(all(p[bf]), p[u][v]) - p[bf].begin();
      update(bf, k - 1, w);
    }

  }
  for(int i = 1; i <= n; i ++) cout << f[i][0] << "\n";
}