//
// Stvoreno ENERGom o 11.04.24. 15:06:59
//
#include <bits/stdc++.h>
#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define F first
#define fir first
#define S second
#define sec second
#define mp make_pair
#define MP make_pair
#define pb push_back
#define PB push_back
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
#ifdef Energy
#define DEBUG for (int _____DEBUG=1;_____DEBUG;_____DEBUG=0)
template<class ...Ts>
auto &PRNT(Ts ...ts) { return ((cerr << ts << " "), ...); }
#define LOG(...) PRNT(#__VA_ARGS__" ::",__VA_ARGS__)<<endl
#else
#define DEBUG while (0)
#define LOG(...)
#endif
const int max_n = 2e5+10, inf = 1000111222;
struct segment_tree {
int T[4 * max_n];
int T_min[4 * max_n];
int T_max[4 * max_n];
void update(int v, int l, int r, int pos, int val) {
if (l == r) {
T[v] += val;
T_min[v] += val;
T_max[v] += val;
return;
}
int m = (l + r) / 2;
if (pos <= m) {
update(2 * v, l, m, pos, val);
} else {
update(2 * v + 1, m + 1, r, pos, val);
}
T[v] = T[v * 2] + T[v * 2 + 1];
T_min[v] = min(T_min[2 * v], T_min[2 * v + 1]);
T_max[v] = max(T_max[2 * v], T_max[2 * v + 1]);
}
int get_sum(int v, int l, int r, int tl, int tr) {
if (l > tr || r < tl) {
return 0;
}
if (l >= tl && r <= tr) {
return T[v];
}
int m = (l + r) / 2;
return get_sum(2 * v, l, m, tl, tr) +
get_sum(2 * v + 1, m + 1, r, tl, tr);
}
int get_righttest_not_minus_one(int v, int l, int r, int tl, int tr)
{
if (l > tr || r < tl) {
return -1;
}
if (l >= tl && r <= tr) {
if (T_max[v]!=-1){
while (l!=r){
int m=(l+r)/2;
if (T_max[2*v+1]!=-1){
v=2*v+1;
l=m+1;
}
else if (T_max[2*v]!=-1){
v=2*v;
r=m;
}
else{
assert(0);
}
}
return l;
}
else{
return -1;
}
}
int m = (l + r) / 2;
int res=get_righttest_not_minus_one(2 * v + 1, m + 1, r, tl, tr);
if (res==-1){
res=get_righttest_not_minus_one(2 * v, l, m, tl, tr);
}
return res;
}
int get_lefttest_not_one(int v, int l, int r, int tl, int tr)
{
if (l > tr || r < tl) {
return -1;
}
if (l >= tl && r <= tr) {
if (T_min[v]!=1){
while (l!=r){
int m=(l+r)/2;
if (T_min[2*v]!=1){
v=2*v;
r=m;
}
else if (T_min[2*v+1]!=1){
v=2*v+1;
l=m+1;
}
else{
assert(0);
}
}
return l;
}
else{
return -1;
}
}
int m = (l + r) / 2;
int res=get_lefttest_not_one(2 * v, l, m, tl, tr);
if (res==-1){
res=get_lefttest_not_one(2 * v + 1, m + 1, r, tl, tr);
}
return res;
}
};
segment_tree st;
int main() {
freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
int n,m,s;
cin>>n>>m>>s;
s--;
vector<pii> guys;
guys.reserve(m);
for (int i=0;i<m;i++){
int d,t;
cin>>d>>t;
t--;
guys.pb(mp(d,t));
}
sort(all(guys));
reverse(all(guys));
/// magic
auto magic___sum_of_differences=[&](int l,int r)
{
return st.get_sum(1,0,n-1,l,r);
};
int magic_value_of_zero=0;
auto magic_get=[&](int pos)
{
assert(0<=pos && pos<n);
return magic_value_of_zero+(pos==0?0:magic___sum_of_differences(0,pos-1));
};
auto magic___increment_difference_naive=[&](int pos,int val)
{
st.update(1,0,n-1,pos,val);
};
auto magic_increment_on_segment=[&](int l,int r,int val)
{
magic___increment_difference_naive((l-1+n)%n,+val);
magic___increment_difference_naive(r,-val);
if (l<=0 && r>=0){
magic_value_of_zero+=val;
}
};
auto magic_set_naive=[&](int pos,int val)
{
assert(0<=pos && pos<n);
if (pos==0){
magic___increment_difference_naive(0,+magic_value_of_zero-val);
magic___increment_difference_naive(n-1,-magic_value_of_zero+val);
magic_value_of_zero=val;
}
else{
const int before=magic_get(pos);
magic___increment_difference_naive(pos,+before-val);
magic___increment_difference_naive((pos-1+n)%n,-before+val);
}
};
auto magic_init=[&](vector<int> init_ans)
{
for (int i=0;i<n;i++){
magic_set_naive(i,init_ans[i]);
}
};
auto magic_do_smart_to_left=[&](int pos)
{
LOG("magic_do_smart_to_left");
int prev_val=magic_get((pos-1+n)%n);
int my_val=magic_get(pos);
auto get_best_to_left_local=[&](int pos)
{
if (pos==0){
return 0;
}
LOG("doing ",pos,st.get_righttest_not_minus_one(1,0,n-1,0,pos-1));
return st.get_righttest_not_minus_one(1,0,n-1,0,pos-1)+1;
// while (pos>0 && NAIVE_diff[pos-1]==-1){
// pos--;
// }
// return pos;
};
if (prev_val>my_val+1){
LOG("doing 1");
assert(prev_val==my_val+2);
int best_good=get_best_to_left_local((pos-1+n)%n);
LOG(best_good);
magic_increment_on_segment(best_good,(pos-1+n)%n,-1);
if (best_good==0){
LOG("doing 2");
const int first_val=magic_get(0);
const int last_val=magic_get(n-1);
if (last_val>first_val+1){
LOG("doing 3");
assert(last_val==first_val+2);
best_good=get_best_to_left_local(n-1);
LOG(best_good);
magic_increment_on_segment(best_good,n-1,-1);
}
}
}
};
auto magic_do_smart_to_right=[&](int pos)
{
LOG("magic_do_smart_to_right");
int nxt_val=magic_get((pos+1+n)%n);
int my_val=magic_get(pos);
auto get_best_to_right_local=[&](int pos)
{
if (pos==n-1){
return n-1;
}
int res=st.get_lefttest_not_one(1,0,n-1,pos,n-1);
if (res==-1){
return n-1;
}
else {
return res;
}
// while (pos>0 && NAIVE_diff[pos-1]==-1){
// pos--;
// }
// return pos;
};
if (nxt_val>my_val+1){
LOG("doing 1");
assert(nxt_val==my_val+2);
int best_good=get_best_to_right_local((pos+1+n)%n);
LOG(best_good);
magic_increment_on_segment(best_good,(pos-1+n)%n,-1);
if (best_good==n-1){
LOG("doing 2");
const int first_val=magic_get(0);
const int last_val=magic_get(n-1);
if (first_val>last_val+1){
LOG("doing 3");
assert(first_val==last_val+2);
best_good=get_best_to_right_local(0);
LOG(best_good);
magic_increment_on_segment(0,best_good,-1);
}
}
}
};
/// magic
vector<int> ans(n);
for (int i=0;i<n;i++){
ans[i]=min(abs(i-s),n-abs(i-s));
}
magic_init(ans);
DEBUG{
cerr<<"init"<<"\n";
for (int i=0;i<n;i++){
cerr<<ans[i]<<" ";
}
cerr<<"\n";
};
for (auto i:guys){
const int pos=i.sec;
const int nxt=(pos+1)%n;
LOG(pos,nxt);
int pos_val=magic_get(pos);
int nxt_val=magic_get(nxt);
if (pos_val==nxt_val){
continue;
}
assert(abs(pos_val-nxt_val)==1);
{
swap(pos_val,nxt_val);
magic_set_naive(pos,pos_val);
magic_set_naive(nxt,nxt_val);
}
if (pos_val<nxt_val){
const int nxt_nxt_val=magic_get((nxt+1)%n);
if (nxt_val>nxt_nxt_val+1){
magic_set_naive(nxt,nxt_nxt_val+1);
nxt_val=nxt_nxt_val+1;
}
magic_do_smart_to_left(pos);
// int cur=(pos-1+n)%n;
// while (ans[cur]>ans[(cur+1)%n]+1){
// ans[cur]=ans[(cur+1)%n]+1;
// cur=(cur-1+n)%n;
// }
}
else{
const int prev_pos_val=magic_get((pos-1+n)%n);
if (pos_val>prev_pos_val+1){
magic_set_naive(pos,prev_pos_val+1);
pos_val=prev_pos_val+1;
}
magic_do_smart_to_right(nxt);
// int cur=(nxt+1+n)%n;
// while (ans[cur]>ans[(cur-1)%n]+1){
// ans[cur]=ans[(cur-1)%n]+1;
// cur=(cur+1+n)%n;
// }
}
DEBUG{
for (int i=0;i<n;i++){
cerr<<magic_get(i)<<" ";
}
cerr<<"\n";
cerr<<"diffs are :: "<<"\n";
for (int i=0;i<n;i++){
cerr<<st.get_sum(1,0,n-1,i,i)<<" ";
}
cerr<<"\n";
};
}
for (int i=0;i<n;i++){
cout<<magic_get(i)<<"\n";
}
exit(0);
}
/home/icpc/workspace/WF/WF21/cmake-build-debug/WF21
init
2 3 3 2 1 0 1
pos,nxt :: 4 5
"magic_do_smart_to_left" :: magic_do_smart_to_left
"doing 1" :: doing 1
"doing ",pos,st.get_righttest_not_minus_one(1,0,n-1,0,pos-1) :: doing 3 1
best_good :: 2
2 3 2 1 0 1 1
diffs are ::
1 -1 -1 -1 1 0 1
pos,nxt :: 6 0
"magic_do_smart_to_right" :: magic_do_smart_to_right
"doing 1" :: doing 1
best_good :: 1
1 2 1 0 -1 0 1
diffs are ::
1 -1 -1 -1 1 1 0
pos,nxt :: 2 3
"magic_do_smart_to_left" :: magic_do_smart_to_left
"doing 1" :: doing 1
"doing ",pos,st.get_righttest_not_minus_one(1,0,n-1,0,pos-1) :: doing 1 0
best_good :: 1
1 1 0 0 -1 0 1
diffs are ::
0 -1 0 -1 1 1 0
pos,nxt :: 2 3
pos,nxt :: 0 1
1
1
0
0
-1
0
1
Process finished with exit code 0