#include<bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define eb emplace_back
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define umap unordered_map
#define uset unordered_set
#define mset multiset
#define ui unsigned int
#define ull unsigned ll
#define i128 __int128
using namespace std;

namespace qiqi {
	const ll V = 1<<30;
	ll seed,add;
	ll get() {
		return seed = (seed*239017+add)%V;
	}
	void main() {
		int n,m;
		cin >> n >> m >> seed >> add;
		vll a(n*2),s(n*2+1);
		for (int i = 0; i < n; i++) {
			a[i] = get();
			a[i+n] = a[i]+V;
		}
		ranges::sort(a);
		for (int i = 0; i < n*2; i++) {
			s[i+1] = s[i]+a[i];
		}
		ll ans = *ranges::partition_point(views::iota(0ll,n*V+1),[&](ll x) {
			vll nxt(n*2);
			for (int l = 0,r = -1; l < n; l++) {
				auto calc = [&](int l,int r) {
					int mid = l+((r-l)>>1);
					return (mid-l)*a[mid]-(s[mid]-s[l])+(s[r]-s[mid])-(r-mid)*a[mid];
				};
				while (r < n*2 && calc(l,r+1) <= x) {
					r++;
				}
				nxt[l] = r;
				nxt[l+n] = nxt[l]+n;
			}
			pii mn(V,-1);
			for (int i = 0; i < n; i++) {
				mn = min(mn,pii(nxt[i]-i,i));
			}
			for (int i = mn.se; i <= nxt[mn.se]; i++) {
				for (int j = 0,p = i%n; j < m; j++) {
					p = nxt[p];
					if (p >= (i%n)+n) {
						return 0;
					}
				}
			}
			return 1;
		});
		cout << ans << '\n';
	}
}

int main() {
//	clock_t st = clock();
//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int T = 1;
//	cin >> T;
	while (T--) {
		qiqi::main();
	}

//	cout << (double)(clock()-st)/CLOCKS_PER_SEC;
	return 0;
}