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.*;
import java.util.*;

public class D {

	static int [] w ; 
	
	static ArrayList<Integer> primes;
	static int[] isComposite;
	static int [] phi ; 
	
	static void sieve(int N) {
		isComposite = new int[N + 1];
		isComposite[0] = isComposite[1] = 1;
		primes = new ArrayList<Integer>();

		for (int i = 2; i <= N; ++i)
			if (isComposite[i] == 0) {
				primes.add(i);
				if (1l * i * i <= N)
					for (int j = i * i; j <= N; j += i)
						isComposite[j] = 1;
			}
	}
	
	
	static int tower(int mod , int l , int r )
	{
		
		if(phi[mod] == 1 || l == r) return w[l] ; 
		
		int x  = tower(mod + 1, l + 1, r ) ; 
		
		return modPow(w[l] , x , phi[mod]) ; // a ^ (phi(m) + x mod phi(m))   mod m ; 
	
	}
	
	static int modPow(int a, int e, long mod) {
	    long ans = 1;
	    
	    while (e > 0) {
	        if ((e & 1) != 0) 
	        {
	            if(ans >= mod / a)
	            	ans  = (ans * a) % mod + mod ; 
	            else
	            	ans = ans * a ; 
	            
	        }
	        
	        if(a  >= mod / a)
	        	a = (int)((1l*a * a) % mod + mod) ;
	        else 
	        	a = a * a ; 
	        
	        e >>= 1;
	    }
	    return (int)ans ;
	}
	
	static int phi(int N)
	{
		int ans = N; int idx = 0 ; long p = primes.get(0);
		while(p * p <= N)
		{
			if(N % p == 0)
				ans -= ans / p;
			while(N % p == 0)
				N /= p;
			p = primes.get(++idx);
		}
			
		if(N != 1) 
			ans -= ans / N;
		return ans;
	}

	
	public static void main(String[] args) throws Exception 
	{
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		sieve((int)1e7);
		int n = sc.nextInt() , m = sc.nextInt();
		
		w = new int [n + 1] ; 
		phi = new int [(int)1e6] ; 
		phi[0] = m ; 
		
		for(int i = 1 ; i < 1e6 ; i++)phi[i] = phi(phi[i - 1]) ; 
		
		for(int i = 1 ; i <= n ;i++)w[i] = sc.nextInt();
		
		int q = sc.nextInt();
		
		while(q-->0)
		{
			int l = sc.nextInt() , r = sc.nextInt() ; 
			if(l == r)
				out.println(w[l] % m);
			else
				out.println(tower( 0 , l , r ) % m);

			
		}
		
		out.flush();
		out.close();

	}

	static class Scanner {
		BufferedReader br;
		StringTokenizer st;

		Scanner(InputStream in) {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() throws Exception {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		int nextInt() throws Exception {
			return Integer.parseInt(next());
		}

		long nextLong() throws Exception {
			return Long.parseLong(next());
		}

		double nextDouble() throws Exception {
			return Double.parseDouble(next());
		}

	}

	static void shuffle(int[] a) {
		int n = a.length;
		for (int i = 0; i < n; i++) {
			int r = i + (int) (Math.random() * (n - i));
			int tmp = a[i];
			a[i] = a[r];
			a[r] = tmp;
		}
	}

}