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 Main {
    public static void main(String args[]) throws IOException{
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        
        int n = in.readInt();
        int m = in.readInt();
        
        Solution sol = new Solution(n, m);
        for(int i=1; i<=n; ++i){
            sol.push(i, in.readInt());
        }
        
        int q = in.readInt();
        while(q-- > 0){
            int l = in.readInt();
            int r = in.readInt();
            if(m==1){
                out.println(0);
                continue;
            }
            out.println(sol.solve(l,r,0)%m);
        }
        out.close();
        // System.out.println(sol.v[0]);
        // Solution sol = new Solution(10,10);
        // sol.overflow(1, 1,1);
        
    }
}

class Solution {
    int[] v = new int[100009];
    int[] a;
    int n;
    int m;
    int cnt;
    boolean ovf;
    
    int power(int base, int b, int m){
        ovf = false;
        if(m == 0)
            return 0;
        if(b == 0 || base == 1)
            return 1;

        long x = 1;
        long a = base; 
        while(b > 0){
            if((b&1) == 1){
                if(a >= m || x*a >= m)
                    ovf = true;
                x = (x*a) % m;
            }
            if(a*a >=m && b > 1)
                ovf = true;
            a = (a*a)%m;
            b >>=1;
        }
        return (int) x;
    }
    
    int phi(int n){
        int ret=n;
        for(int i=2;i*i<=n;i++){
            if(n%i==0){
                while(n%i==0)n/=i;
                ret-=ret/i;
            }
        }
        if(n>1)ret-=ret/n;
        return ret;
    }
    
    long solve(int l, int r, int k){
        if (l>r || k + 1 >= cnt)
		    return 1;
    	long temp = solve(l+1, r, k+1);
    	long x = a[l];
    	long ret = 1;
    	while(temp > 0)
    	{
    		if ((temp&1) == 1)
    			ret = modulo(ret*x, v[k]);
    		x = modulo(x*x, v[k]);
    		temp>>=1;
    	}
    	return ret;
    }
    
    long modulo(long a, long b){
        if (a<b)
		    return a;
	    return (a%b)+b;
    }
    
    // int overflow(int base, int b, int m){
    //     long x = 1;
    //     long a = base; 
    //     while(b > 0){
    //         if((b&1) == 1){
    //             if(a < 0 || a >= m)
    //                 return m;
    //             x = (x*a);
    //             if(x >= m)
    //                 return m;
    //         }
    //         a = (a*a);
    //         b >>=1;
    //     }
    //     return (int) x;
    // }
    
    
    // int solve(int l, int r, int k){
    //     boolean usehack = false;
    //     int running = 1;
    //     int running2 = 1;
         
    //     for(int i = r; i >= l; --i){
    //         if(i - l + 1 >= cnt){
    //             v[i-l] = 1;
    //             v[i-l+1] = 1;
    //         }
    //         if(a[i] == 1){
    //             running = 1;
    //             usehack = false;   
    //         }
    //         else if(!usehack && running < v[i-l+1]){
    //             running = power(a[i], running, v[i-l]);
    //             if(ovf == true)
    //                 usehack = true;
    //         }
    //         else {
    //             usehack = true;
    //             running = power(a[i], v[i-l+1] + running%v[i-l+1], v[i-l]);
    //         }
            
    //     }
        
    //     return running;
    // }
    
    
    
    void push(int id, int x){
        a[id] = x;
    }
    
    Solution(int n, int m){
        this.m = m;
        a = new int[n + 1];
        v[0] = m;
        cnt = 1;
        while(m!=1){
            m = phi(m); 
            v[cnt++] = m;
        }
    }
}



// fast I/O
class InputReader {
	private InputStream stream;
	private byte[] buf = new byte[1024];
	private int curChar;
	private int numChars;

	public InputReader(InputStream stream) {
		this.stream = stream;
	}

	public int read() {
		if (numChars == -1)
			throw new InputMismatchException();
		if (curChar >= numChars) {
			curChar = 0;
			try {
				numChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (numChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public int readInt() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public static boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	public char readCharacter() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		return (char) c;
	}
}

class OutputWriter {
	private final PrintWriter writer;

	public OutputWriter(OutputStream outputStream) {
		writer = new PrintWriter(outputStream);
	}

	public OutputWriter(Writer writer) {
		this.writer = new PrintWriter(writer);
	}

	public void print(Object...objects) {
		for (int i = 0; i < objects.length; i++) {
			if (i != 0)
				writer.print(' ');
			writer.print(objects[i]);
		}
	}

	public void println(Object...objects) {
		print(objects);
		writer.println();
	}

	public void close() {
		writer.close();
	}
}