#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;

#define fr first
#define sc second

const int INF=1000000000;

struct SEG{
    int siz;
    int s[1<<18];
    void init(){
        siz = 1<<17;
        for(int i=0;i<2*siz-1;i++){
            s[i]=INF;
        }
    }
    void updata(int a,int b,int x,int k,int l,int r){
        if(b <= l || r <= a)return;
        if(a <= l && r <= b){
            s[k] = min ( s[k] , x );
            return;
        }
        updata(a,b,x,2*k+1,l,(l+r)/2);
        updata(a,b,x,2*k+2,(l+r)/2,r);
    }
    void _updata(int a,int x){
        int l=a,r=a+1,m=a;
        a += siz-1;
        s[a] = x;
        while(a > 0){
            if(a%2 == 0){
                l -= r-l;
            }
            else {
                r += r-l;
            }
            a = (a-1)/2;
            updata(l,m,s[a],a,l,r);
            updata(m+1,r,s[a],a,l,r);
            s[a] = INF;
        }
    }
    int query(int a){
        a += siz-1;
        int ret = s[a];
        while(a > 0){
            a = (a-1)/2;
            ret = min ( ret , s[a] );
        }
        return ret;
    }
}dp[2];

int main(){
    int T;
    scanf("%d",&T);
    for(int test=0;test<T;test++){
        static int n,m,k;
        static int h[100010],x[100010];
        scanf("%d%d%d",&n,&m,&k);
        for(int i=0;i<m;i++){
            scanf("%d%d",&h[i],&x[i]);
        }
        
        pair<int,int> p[100010];
        for(int i=0;i<m;i++){
            p[i]=pair<int,int>(h[i],x[i]);
        }
        sort(p,p+m);
        
        dp[0].init();
        dp[1].init();
        dp[0].updata(k,n+1,-k,0,0,dp[0].siz);
        dp[1].updata(1,k+1,k,0,0,dp[1].siz);
        
        
        /*static vector<int> G[100010];
        static int a[100010];
        a[0]=0;     G[0].clear();
        a[n+1]=n+1; G[n+1].clear();
        for(int i=1;i<=n;i++){
            a[i]=i;
            G[i].clear();
            G[i].push_back(i-1);
            G[i].push_back(i+1);
        }*/
        
        int t=0;
        int now=k;
        for(int i=0;i<m;i++){
            int c[2] = {1,-1};
            if(p[i].sc == now)now++;
            else if(p[i].sc+1 == now)now--;
            for(int j=0;j<2;j++){
                //int memo=min(dp[j].query(p[i].sc),dp[j].query(p[i].sc+1)+c[j]);
                //dp[j].updata(p[i].sc,p[i].sc+1,memo,0,0,dp[j].siz);
                //dp[j].updata(p[i].sc+2,p[i].sc+1,memo-c[j],0,0,dp[j].siz);
                int memo=dp[j].query(p[i].sc);
                dp[j]._updata(p[i].sc,min(dp[j].query(p[i].sc+1)+c[j],abs(now-p[i].sc)-p[i].sc*c[j]));
                dp[j]._updata(p[i].sc+1,min(memo-c[j],abs(now-p[i].sc-1)-(p[i].sc+1)*c[j]));
                //if(j == 1)cout << p[i].sc+1 << " " << memo-c[j] << endl;
            }
            
            /*for(int j=1;j<=n;j++){
                printf("%d ",dp[0].query(j)+j);
                cout << endl;
            }
            for(int j=1;j<=n;j++){
                printf("%d ",dp[1].query(j)-j);
                cout << endl;
            }*/
            
            if(i+1<m&&p[i].fr==p[i+1].fr)continue;
            for(;t<=i;t++){
                dp[0].updata(p[t].sc+1,n+1,min(dp[0].query(p[t].sc+1),dp[1].query(p[t].sc+1)-2*(p[t].sc+1)),0,0,dp[0].siz);
                dp[1].updata(1,p[t].sc+2,min(dp[0].query(p[t].sc+1)+2*(p[t].sc+1),dp[1].query(p[t].sc+1)),0,0,dp[0].siz);
                dp[0].updata(p[t].sc,n+1,min(dp[0].query(p[t].sc),dp[1].query(p[t].sc)-2*p[t].sc),0,0,dp[1].siz);
                dp[1].updata(1,p[t].sc+1,min(dp[0].query(p[t].sc)+2*p[t].sc,dp[1].query(p[t].sc)),0,0,dp[1].siz);
                dp[0].updata(p[t].sc-1,n+1,min(dp[0].query(p[t].sc-1),dp[1].query(p[t].sc-1)-2*(p[t].sc-1)),0,0,dp[0].siz);
                dp[1].updata(1,p[t].sc,min(dp[0].query(p[t].sc-1)+2*(p[t].sc-1),dp[1].query(p[t].sc-1)),0,0,dp[0].siz);
                dp[0].updata(p[t].sc+2,n+1,min(dp[0].query(p[t].sc+2),dp[1].query(p[t].sc+2)-2*(p[t].sc+2)),0,0,dp[1].siz);
                dp[1].updata(1,p[t].sc+3,min(dp[0].query(p[t].sc+2)+2*(p[t].sc+2),dp[1].query(p[t].sc+2)),0,0,dp[1].siz);
            }
            
            /*G[a[p[i].sc-1]].push_back(a[p[i].sc]);
            G[a[p[i].sc]].push_back(a[p[i].sc-1]);
            G[a[p[i].sc+1]].push_back(a[p[i].sc+2]);
            G[a[p[i].sc+2]].push_back(a[p[i].sc+1]);*/
        }
        
        for(int i=1;i<=n;i++){
            //if(dp[0].query(i)+i==0){
                dp[0].updata(i,n+1,min(dp[0].query(i)+i,dp[1].query(i)-i)-i,0,0,dp[0].siz);
                dp[1].updata(1,i+1,min(dp[0].query(i)+i,dp[1].query(i)-i)+i,0,0,dp[1].siz);
            //}
        }
        
        for(int i=1;i<=n;i++){
            printf("%d%c",min(dp[0].query(i)+i,dp[1].query(i)-i),10);
        }
        /*for(int i=0;i<100010;i++){
            ans[i]=100010;
        }
        ans[a[k]]=0;
        
        queue<int> que;
        que.push(a[k]);
        while(!que.empty()){
            int s=que.front(); que.pop();
            for(int i=0;i<G[s].size();i++){
                if(ans[G[s][i]]==100010){
                    ans[G[s][i]]=ans[s]+1;
                    que.push(G[s][i]);
                }
            }
        }
        
        for(int i=1;i<=n;i++){
            printf("%d%c",ans[i],10);
        }*/
    }
}

Measured memory_bytes: 6780