func main() var n: int :: cui@inputInt() var m: int :: cui@inputInt() var p: int :: cui@inputInt() var q: int :: cui@inputInt() for(1, q) var x: int :: cui@inputInt() var f: int :: cui@inputInt() var ans: int :: 0 if(x % p = 0) if(f = 0) do ans :: m else do ans :: m / f end if else var target: int :: f * math@modPow(x, p - 2, p) % p do ans :: m / p if(f <> 0) do ans :+ (m % p < target ?(0, 1)) end if end if do cui@print("\{ans}\n") end for end func