N,M,P,Q = map(int,input().split())

ANS = []

for lp in range(Q):

    x,f = map(int,input().split())

    y = ( f * pow(x,P-2,P) ) % P
    if y == 0:
        y += P


    l = -1
    r = 10**18

    while r-l != 1:

        m = (l+r)//2

        if m * P + y <= M:
            l = m
        else:
            r = m

    ANS.append(r)
    
print (*ANS,sep="\n")