Problem: Priests 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 wk then value of power of a new tower will be {wk}p. 

Rocks are added from the last to the first. That is for sequence w1, ..., wm value of power will be

<image>

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 ≤ 105) and m (1 ≤ m ≤ 109).

Second line of input contains n integers wk (1 ≤ wk ≤ 109) which is the power of rocks that priests have.

Third line of input contains single integer q (1 ≤ q ≤ 105) which is amount of queries from priests to you.

kth of next q lines contains two integers lk and rk (1 ≤ lk ≤ rk ≤ 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 lk, lk + 1, ..., rk.

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

327 = 7625597484987

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Div1_454D {

	static long[] items;
	static long[] mods;

	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter printer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

		StringTokenizer inputData = new StringTokenizer(reader.readLine());
		int nI = Integer.parseInt(inputData.nextToken());
		long bMod = Integer.parseInt(inputData.nextToken());

		items = new long[nI];

		inputData = new StringTokenizer(reader.readLine());
		for (int i = 0; i < nI; i++) {
			items[i] = Integer.parseInt(inputData.nextToken());
		}

		mods = new long[50];

		mods[0] = bMod;

		for (int i = 1; mods[i - 1] != 1; i++) {
			mods[i] = phi(mods[i - 1]);
		}

		int nQ = Integer.parseInt(reader.readLine());

		while (nQ-- > 0) {
			inputData = new StringTokenizer(reader.readLine());
			int l = Integer.parseInt(inputData.nextToken()) - 1;
			int r = Integer.parseInt(inputData.nextToken()) - 1;
			printer.println(calc(l, r, 0) % bMod);
		}
		printer.close();
	}

	static long calc(int l, int r, int mI) {
		if (l == r + 1) {
			return 1;
		}
		if (mods[mI] == 1) {
			return items[l];
		}
		return exp(items[l], calc(l + 1, r, mI + 1), mods[mI]);
	}

	static long phi(long num) {
		long ans = 1;
		for (int i = 2; i * i <= num; i++) {
			if (num % i == 0) {
				while (num % i == 0) {
					num /= i;
					ans *= i;
				}
				ans = ans / i * (i - 1);
			}
		}
		if (num != 1) {
			ans *= (num - 1);
		}
		return ans;
	}

	static long exp(long base, long pow, long mod) {
		long ans = 1;
		while (pow > 0) {
			if ((pow & 1) != 0) {
				ans = ans * base;
				if (ans >= mod) {
					ans = ans % mod + mod;
				}
			}
			base = base * base;
			if (base >= mod) {
				base = base % mod + mod;
			}
			pow >>= 1;
		}
		return ans;
	}

}