#include<bits/stdc++.h> using namespace std; #define int long long const int N=5e5+10,INF=0x3f3f3f3f; int n,p,m,state; int a[N],b[N],c[N]; int vis[N]; struct node{ int val,laz; }tr[N<<2],tr0[N<<2]; int ans; vector<int> S[N],T[N]; void pushUp(int x){ tr0[x].val=tr0[x<<1].val+tr0[(x<<1)|1].val; } void build(int l,int r,int x){ if(l==r){ tr0[x].val=c[l]; return ; } int mid=(l+r)>>1; build(l,mid,x<<1); build(mid+1,r,(x<<1)|1); pushUp(x); } void update(int x){ if(tr[x].laz) tr[x].val=tr0[x].val; else tr[x].val=tr[x<<1].val+tr[(x<<1)|1].val; } void modify(int s,int t,int l,int r,int x,int k){ if(l<=s&&t<=r){ tr[x].laz+=k; update(x); return ; } if(s>r||t<l) return ; int mid=(s+t)>>1; if(t>=l) modify(s,mid,l,r,x<<1,k); if(s<r) modify(mid+1,t,l,r,(x<<1)|1,k); update(x); } int getans(){ return tr[1].val; } void init(){ ans=INF; for(int i=0;i<n;i++){ state=(state*1103515245+12345)%(1LL<<31);//state 需定义为 long long c[i]=1+((state/10)%m); } 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); if(a[i]>b[i]) swap(a[i],b[i]); if(a[i]<b[i]){ S[a[i]].push_back(i); T[b[i]].push_back(i); } } build(0,n-1,1); } signed main(){ scanf("%lld%lld%lld%lld",&n,&p,&m,&state); init(); for(int i=1;i<=p;i++){ if(a[i]<b[i]) modify(0,n-1,a[i],b[i]-1,1,1); } for(int i=0;i<n;i++){ for(auto j : S[i]){ modify(0,n-1,a[j],b[j]-1,1,-1); if(0<a[j]) modify(0,n-1,0,a[j]-1,1,1); if(b[j]<n) modify(0,n-1,b[j],n-1,1,1); } for(auto j : T[i]){ modify(0,n-1,a[j],b[j]-1,1,1); if(0<a[j]) modify(0,n-1,0,a[j]-1,1,-1); if(b[j]<n) modify(0,n-1,b[j],n-1,1,-1); } ans=min(ans,getans()); } printf("%lld",ans); return 0; }