Polynomial Composition Modulo Query

Given a polynomial \[ f(x)=\sum_{i=1}^{m} a_i x^{b_i}, \] we define a sequence of functions as follows: \[ f_1(x)=f(x), \quad f_n(x)=f(f_{n-1}(x))\text{ for } n\ge2. \] For a given modulus \(p\) and \(q\) queries, each query provides two integers \(x\) and \(y\). Your task is to compute \(f_y(x)\bmod p\) for each query.

Note: Special care must be given to the constraints on \(m\) and \(p\).

inputFormat

The first line contains three integers \(m\), \(p\) and \(q\). The following \(m\) lines each contain two integers \(a_i\) and \(b_i\), representing the polynomial \(f(x)=\sum_{i=1}^{m} a_i x^{b_i}\). Then \(q\) lines follow, each containing two integers \(x\) and \(y\) which represent a query asking for \(f_y(x) \bmod p\).

outputFormat

For each query, output a single integer, the value of \(f_y(x) \bmod p\), on a separate line.

sample

2 100 3
1 1
1 2
2 1
2 2
3 3

6
42
92