#include using namespace std; #ifdef LOCAL #include "settings/debug.cpp" #else #define Debug(...) void(0) #endif #define rep(i, n) for (int i = 0; i < (n); ++i) using ll = long long; using ull = unsigned long long; #include using mint = atcoder::modint; int find(int p, int t, int m) { int ok = 0, ng = m; while (ng - ok > 1) { ll mid = ((ll) ok + ng) / 2; (p * (mid - 1) + t <= m ? ok : ng) = mid; } return ok; } int main() { int n, m, p, q; cin >> n >> m >> p >> q; mint::set_mod(p); while (q--) { int x, f; cin >> x >> f; if (x % p == 0) { cout << (f == 0 ? m : 0) << endl; } else { mint a = mint(x).inv() * f; Debug(x, f, a.val()); if (a.val() == 0) { cout << find(p, 0, m) - 1 << endl; } else { cout << find(p, a.val(), m) << endl; } } } return 0; }