Redstone Modular Computation

Dream built a redstone computer to verify formulas of the form \(b^e \equiv r \pmod{m}\). He fixed the base \(b\) and the modulus \(m\), and then generated \(n\) pairs of positive integers \((e, r)\) such that the congruence holds. Unfortunately, he forgot the actual value of \(m\). Now, he gives you \(b\) and these \(n\) pairs. Your task is to substitute for Dream's computer and answer \(q\) queries of the form \(b^{a_i} \bmod m\).

Hint: Since for each given pair \((e, r)\), we have \[ b^e \equiv r \pmod{m}, \] it follows that \(m\) divides \(b^e - r\) for every \((e, r)\). Hence, \(m\) is a divisor of the greatest common divisor (gcd) of the numbers \(b^e - r\) over all pairs. You may deduce \(m\) as this gcd. Then, answer each query by computing \(b^{a_i} \bmod m\).

inputFormat

The input begins with two integers \(b\) and \(n\) on the first line. The next \(n\) lines each contain two positive integers \(e\) and \(r\) representing a pair such that \(b^e \equiv r \pmod{m}\). The following line contains a positive integer \(q\), representing the number of queries. Each of the next \(q\) lines contains a positive integer \(a_i\), for which you need to compute \(b^{a_i} \bmod m\).

Input Format Summary:

• First line: two integers \(b\) and \(n\).
• Next \(n\) lines: each line contains two integers \(e\) and \(r\).
• Next line: an integer \(q\).
• Next \(q\) lines: each line contains a single integer \(a_i\).

outputFormat

For each query, output the value of \(b^{a_i} \bmod m\) on a new line.

sample

2 2
3 3
4 1
2
3
4

3
1