#include<bits/stdc++.h> using namespace std; #define int long long #define ls pos<<1 #define rs pos<<1|1 const int N=5e5+10,P=1e5+10; int n,p,m,state,ans,c[N],pre[N],a[P],b[P]; bool vis[N]; vector<int>q[N];//经过这一条边的 void init(){ for (int i=1;i<=n;i++) { state=(state*1103515245+12345)%(1LL<<31);//state 需定义为 long long c[i]=1+((state/10)%m); //pre[i]:1->i的距离 pre[i]=pre[i-1]+c[i]; } for (int i=1;i<=p;i++) { state=(state*1103515245+12345)%(1LL<<31); a[i]=((state/10)%n); state=(state*1103515245+12345)%(1LL<<31); b[i]=((state/10)%n); a[i]++;b[i]++; if(a[i]>b[i]){int sw=a[i];a[i]=b[i];b[i]=sw;} q[a[i]].push_back(i); } } //tmp表示当前区间是否全都被覆盖 struct tree{int num,tmp,lz;}t[N<<2]; void pushup(int pos,int l,int r){ if(t[pos].tmp)t[pos].num=pre[r]-pre[l-1]; else t[pos].num=t[ls].num+t[rs].num; } void pushdown(int pos,int l,int r){ if(t[pos].tmp){ int mid=(l+r)>>1; t[ls].num=pre[mid]-pre[l-1];t[ls].lz=1; t[rs].num=pre[r]-pre[mid];t[rs].lz=1; } } void add(int pos,int l,int r,int ql,int qr){//添加区间 //cout<<pos<<endl; if(l>=ql&&r<=qr){ // cout<<l<<" "<<r<<" "; t[pos].num=pre[r]-pre[l-1];t[pos].tmp++; // cout<<t[pos].num<<" "<<t[pos].tmp<<endl; return; } // pushdown(pos,l,r); int mid=(l+r)>>1; if(ql<=mid)add(ls,l,mid,ql,qr); if(qr>mid)add(rs,mid+1,r,ql,qr); pushup(pos,l,r); } void del(int pos,int l,int r,int ql,int qr){//cout<<"%%%%%"<<endl; // cout<<l<<" "<<r<<" "<<ql<<" "<<qr<<endl; if(l>=ql&&r<=qr){//cout<<"lsadguflisdaugfisdugf"<<endl; //cout<<pos<<" "<<t[pos].tmp<<" "; t[pos].tmp--;//cout<<t[pos].tmp<<endl; if(t[pos].tmp==0)t[pos].num=t[ls].num+t[rs].num; return; } // pushdown(pos,l,r); int mid=(l+r)>>1; if(ql<=mid)del(ls,l,mid,ql,qr); if(qr>mid)del(rs,mid+1,r,ql,qr); pushup(pos,l,r); } signed main(){ //freopen("20241002T2.out","w",stdout); cin>>n>>p>>m>>state; init(); // for(int i=1;i<=n;i++)cout<<c[i]<<" "; // cout<<endl; // for(int i=1;i<=p;i++)cout<<a[i]<<" "<<b[i]<<endl; // cout<<endl; for(int i=1;i<=p;i++){ if(a[i]==b[i])continue; add(1,1,n+1,a[i],b[i]-1); } // for(int i=1;i<=n*2;i++)cout<<t[i].num<<" "; // cout<<endl; // for(int i=1;i<=n*2;i++)cout<<t[i].tmp<<" "; // cout<<endl<<endl; ans=t[1].num; for(int i=1;i<=n;i++){//枚举断哪一条边，这样每两点之间的路径唯一 // cout<<"!"<<i<<endl; for(int j:q[i]){ if(a[j]==b[j])continue; if(!vis[j]){ // cout<<"?"<<a[j]<<" "<<b[j]<<endl; vis[j]=1; del(1,1,n+1,a[j],b[j]-1); // for(int i=1;i<=n*2;i++)cout<<t[i].num<<" "; // cout<<endl; // for(int i=1;i<=n*2;i++)cout<<t[i].tmp<<" "; // cout<<endl<<endl; if(a[j]>1)add(1,1,n+1,1,a[j]-1); add(1,1,n+1,b[j],n); // for(int i=1;i<=n*2;i++)cout<<t[i].num<<" "; // cout<<endl; // for(int i=1;i<=n*2;i++)cout<<t[i].tmp<<" "; // cout<<endl<<endl; q[b[j]].push_back(j); ans=min(ans,t[1].num); } else{ if(a[j]>1)del(1,1,n+1,1,a[j]-1); del(1,1,n+1,b[j],n); // for(int i=1;i<=n*2;i++)cout<<t[i].num<<" "; // cout<<endl; // for(int i=1;i<=n*2;i++)cout<<t[i].tmp<<" "; // cout<<endl<<endl; add(1,1,n+1,a[j],b[j]-1); // for(int i=1;i<=n*2;i++)cout<<t[i].num<<" "; // cout<<endl; // for(int i=1;i<=n*2;i++)cout<<t[i].tmp<<" "; // cout<<endl<<endl; ans=min(ans,t[1].num); q[a[j]].push_back(j); } } q[i].clear(); // cout<<"!"<<i<<" "<<t[1].num<<" "<<ans<<endl; // for(int i=1;i<=n*2;i++)cout<<t[i].num<<" "; // cout<<endl; // for(int i=1;i<=n*2;i++)cout<<t[i].tmp<<" "; // cout<<endl<<endl; } cout<<ans<<endl; return 0; }