#include <bits/stdc++.h>
using namespace std;
using ll = long long;

pair<ll, ll> extEucMod(ll a, ll b, ll p) {
	if (b == 0) return {1, 0};
	ll m = a / b;
	auto sub = extEucMod(b, a - b * m, p);
	return {sub.second, (sub.first - m*sub.second) % p};
}
ll modInv(ll a, ll p) {
	ll res = extEucMod(p, a, p).second;
	return (res < 0 ? res + p : res);
}
ll gcd(ll a, ll b) { return (b == 0 ? a : gcd(b, a % b)); }
ll mSub(ll a, ll b, ll m) { return (a >= b ? a - b : a - b + m); }
ll posMod(ll a, ll m) { ll res = a % m; return (res < 0 ? res + m : res); }
ll getSteps(ll t, ll ia, ll b, ll m) { return mSub(t, b, m) * ia % m; }

// Returns minimum value of ax + b (mod m) for x \in [0, k]. O(log m) time
ll minRem(ll a0, ll b0, ll m0, ll k) {
	ll g = gcd(a0, m0);
	if (g > 1) return g * minRem(a0 / g, b0 / g, m0 / g, k) + (b0 % g);
	for (ll a = a0, b = b0, m = m0, ia0 = modInv(a0, m0), s; a; b = s) {
		if (a > m-a) {
			m = m - a;
			s = b % m;
			if (getSteps(s, ia0, b0, m0) > k) {
				ll low = 1, high = (b - s) / m;
				while(low != high) {
					ll mid = (low + high) >> 1;
					if (getSteps(s + m * mid, ia0, b0, m0) <= k) high = mid;
					else low = mid + 1;
				}
				return s + m * low;
			}
			a %= m;
		} else {
			s = (b < a ? b : posMod(b - m, a));
			if (getSteps(s, ia0, b0, m0) > k) return b;

			ll tmp = posMod(-m, a);
			m = a;
			a = tmp;
		}
	}
	return 0;
}

// Returns minimum x such that ax + b (mod m) \in [le, ri] or -1 if there is no such x. O(log m) time
ll firstInRange(ll a, ll b, ll m, ll le, ll ri) {
	ll g = gcd(a, m);
	if (g > 1) {
		le = le / g + (le % g > b % g);
		ri = ri / g - (ri % g < b % g);
		a /= g; b /= g; m /= g;
	}
	if (le > ri) return -1; // impossible
	
	ll ia = modInv(a, m);
	ll x0 = mSub(le, b, m) * ia % m;
	return minRem(ia, x0, m, ri - le);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	ll a0, b0, m0, k;
	cin >> a0 >> b0 >> m0 >> k;
	cout << minRem(a0, b0, m0, k) << '\n';

	/*
	ll a, b, m, le, ri;
	cin >> a >> b >> m >> le >> ri;
	cout << firstInRange(a, b, m, le, ri) << '\n';
	*/
}