Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

chinese remainder theorem

math

number theory

*2700

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Power Tower

time limit per test

4.5 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputPriests of the Quetzalcoatl cult want to build a tower to represent a power of their god. Tower is usually made of power-charged rocks. It is built with the help of rare magic by levitating the current top of tower and adding rocks at its bottom. If top, which is built from *k* - 1 rocks, possesses power *p* and we want to add the rock charged with power *w*_{k} then value of power of a new tower will be {*w*_{k}}^{p}.

Rocks are added from the last to the first. That is for sequence *w*_{1}, ..., *w*_{m} value of power will be

After tower is built, its power may be extremely large. But still priests want to get some information about it, namely they want to know a number called cumulative power which is the true value of power taken modulo *m*. Priests have *n* rocks numbered from 1 to *n*. They ask you to calculate which value of cumulative power will the tower possess if they will build it from rocks numbered *l*, *l* + 1, ..., *r*.

Input

First line of input contains two integers *n* (1 ≤ *n* ≤ 10^{5}) and *m* (1 ≤ *m* ≤ 10^{9}).

Second line of input contains *n* integers *w*_{k} (1 ≤ *w*_{k} ≤ 10^{9}) which is the power of rocks that priests have.

Third line of input contains single integer *q* (1 ≤ *q* ≤ 10^{5}) which is amount of queries from priests to you.

*k*^{th} of next *q* lines contains two integers *l*_{k} and *r*_{k} (1 ≤ *l*_{k} ≤ *r*_{k} ≤ *n*).

Output

Output *q* integers. *k*-th of them must be the amount of cumulative power the tower will have if is built from rocks *l*_{k}, *l*_{k} + 1, ..., *r*_{k}.

Example

Input

6 1000000000

1 2 2 3 3 3

8

1 1

1 6

2 2

2 3

2 4

4 4

4 5

4 6

Output

1

1

2

4

256

3

27

597484987

Note

3^{27} = 7625597484987

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/03/2023 03:18:25 (k2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|