Recovering the Secret Key

Alice and Bob have agreed on a large prime number \(p\), an error range \(err\), and a secret key \(x\) uniformly chosen from \(0 \sim p-1\). In order to verify Alice's identity, Bob generates \(m\) random numbers \(a_i\) (each in \(0 \sim p-1\)) and sends them to Alice. For each \(a_i\), Alice returns an equation of the form

\(a_i x + b_i \equiv c_i \pmod{p}\)

where the error term \(b_i\) is a random integer chosen uniformly from \(-\lceil \frac{err}{2} \rceil\) to \(\lceil \frac{err}{2} \rceil\). The values \(a_i\), \(p\), \(err\) and \(c_i\) are public, while \(x\) and \(b_i\) are secret. Given the intercepted \(m\) equations, your task is to recover the secret key \(x\).

Note: It is guaranteed that a valid \(x\) exists and is unique.

inputFormat

The first line contains three space-separated integers: \(p\) (a prime number), \(err\) (the error range), and \(m\) (the number of equations).

Each of the following \(m\) lines contains two space-separated integers \(a_i\) and \(c_i\), representing the equation \(a_i x + b_i \equiv c_i \pmod{p}\).

outputFormat

Output the recovered secret key \(x\) as an integer.

sample

101 5 3
7 41
3 59
5 100

20