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

public class e{
static class FastReader
    {
        BufferedReader br;
        StringTokenizer st;

        public FastReader()
        {
            br = new BufferedReader(new
                     InputStreamReader(System.in));
        }

        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException  e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

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

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

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

        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }

	public static void main(String args[]){
		FastReader sc=new FastReader();
		int n=sc.nextInt();
		long m=sc.nextInt();
		long phi[]=new long[50];
		phi[0]=m;
		for(int i=1;i<50;i++)
			phi[i]=phi(phi[i-1]);
		
		long w[]=new long[n];
		for(int i=0;i<n;i++)
			w[i]=sc.nextInt();
		int q=sc.nextInt();
		StringBuilder sb=new StringBuilder();;
		while((q--)>0){
			int l=sc.nextInt();
			int r=sc.nextInt();
			l--;r--;
			if(l==r)
			sb.append(w[l]%m+"\n");
			else
			sb.append(calc(w,l,r,phi,0)%m+"\n");
		}
		System.out.print(sb);
	}
	static long phi(long n){
		long ans=n;
		for(long i=2;i*i<=n;i++){
			if(n%i==0){
				while(n%i==0)
					n/=i;
				ans-=ans/i;
			}
		}
		if(n>1)
			ans-=ans/n;
		return ans;
	}
	static long calc(long []w,int l,int r,long []phi,int i){
		if(l==r||phi[i]==1)
			return f(w[l],phi[i]);
		int val=i;
		if(i<50)
			val=i+1;
		long y=calc(w,l+1,r,phi,val);
		return pow(w[l],y,phi[i]);
		
	}
	static long f(long x,long y){
		if(x<y)
			return x;
			return x%y+y;
	}
	static long pow(long x,long y,long m){
		long ans=1;
		while(y>0){
			if((y&1)==1)
				ans=f(ans*x,m);
			x=f(x*x,m);
			y/=2;
		}
		return ans;
	}
}