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
{
    int [] phi , w;

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

    int modPow(long a , int e , int mod)
    {
        long ans = 1 ;
        while(e > 0)
        {
            if((e & 1) != 0)
            {
                ans *= a ;
                if(ans >= mod) ans = ans % mod + mod ;
            }
            a *= a ;
            if(a >= mod)
                a = a % mod + mod ;
            e >>= 1 ;
        }
        return (int)ans ;
    }

    int tower(int l , int r , int mod)
    {
        if(phi[mod] == 1 || l == r)return w[r] ;
        return modPow(w[l] , tower(l + 1 , r , mod + 1) , phi[mod]) ;
    }

    void main() throws Exception
    {
        Scanner sc = new Scanner(System.in) ;
        PrintWriter out = new PrintWriter(System.out) ;
        int n = sc.nextInt() , m = sc.nextInt();
        phi = new int[30] ;
        phi[0] = m ;
        for(int i = 1 ; i < 30 ; i++)
            phi[i] = phi(phi[i - 1]) ;
        w = new int [n] ;
        for(int i = 0 ; i < n ; i++)
            w[i] = sc.nextInt() ;
        int q = sc.nextInt();
        while (q-->0)
            out.println(tower(sc.nextInt() - 1 , sc.nextInt() - 1, 0) % m);
        out.flush();
        out.close();
    }

    class Scanner
    {
        BufferedReader br;
        StringTokenizer st;

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

        Scanner(String path) throws Exception
        {
            br = new BufferedReader(new FileReader(path)) ;
        }
        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());}
    }

    public static void main (String [] args) throws Exception {(new Main()).main();}

}