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 :: 0 end if else var target: int :: f * @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 func modPow(a: int, n: int, mod: int): int var res: int :: 1 while(n <> 0) if(n % 2 = 1) do res :: res * a % mod end if do a :: a * a %mod do n :/ 2 end while ret res end func