Background

I have won everything except your heart.

Finally, Little Z can play Genshin Impact for a year. But before that, he decided to create this problem to commemorate his feelings for [data deleted].

Problem Description

Given a polynomial $f(x)=\sum_{i=1}^m a_i x^{b_i}$. Define $f_1(x)=f(x)$, and $f_n(x)=f(f_{n-1}(x))$.

Given a modulus $p$. There are $q$ queries. Each query gives $x,y$, and asks for the value of $f_y(x)\bmod p$.

Please note the special Constraints for $m,p$.

Input Format

The first line contains three positive integers $m,q,p$, representing the number of terms in $f$, the number of queries, and the given modulus.

Then follow $m$ lines, each containing two non-negative integers $a_i,b_i$, describing the polynomial $f$.

Then follow $q$ lines, each containing two positive integers $x,y$, representing one query.

Output Format

Output $q$ lines in total, each line containing the answer to the corresponding query.

3 5 71
1 1
3 3
1 0
7 5
9 6
10 1
5 6
7 6

27
11
29
2
5

Hint

Explanation of the Samples

In Sample 1, $f(x)=3x^3+x+1$. Take the 3rd query as an example: $f_1(10)=f(10)=3\times10^3+10+1=3011\equiv 29 \pmod {71}$.

Constraints and Conventions

• Special Property A: $p$ is guaranteed to be a prime.
• Special Property B: $b_i\le 1$ is guaranteed.

For all testdata, it is guaranteed that $1\le m\le 20$, $0\le a_i,b_i\le 10^5$, $2\le p\le 10^5$, $1\le q\le 3\times 10^5$, and $1\le x,y\le 10^7$.

Translated by ChatGPT 5