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.Arrays;

public class Main {
  private static void solve() {
    int n = ni();
    long m = nl();
    long[] tot = new long[1000];
    tot[0] = m;
    for (int i = 1; i < tot.length; i++) {
      tot[i] = totient(tot[i - 1]);
      if (tot[i] == 1) {
        tot = Arrays.copyOf(tot, i + 1);
        break;
      }
    }
    int p = tot.length;

    long[] w = nal(n);
    int q = ni();
    for (int i = 0; i < q; i++) {
      int l = ni() - 1;
      int r = ni() - 1;

      int d = Math.min(r - l, p);
      long ret = w[r];
      for (int j = d - 1; j >= 0; j--) {
        ret = powv(w[l + j], ret, tot[j]);
      }
      ret %= m;
      out.println(ret);
    }
  }

  public static long powv(long a, long n, long mod) {
    long ret = 1;
    int x = 63 - Long.numberOfLeadingZeros(n);
    for (; x >= 0; x--) {
      ret = mulv(ret, ret, mod);
      if (n << ~x < 0)
        ret = mulv(ret, a, mod);
    }
    return ret;
  }

  public static long mulv(long x, long y, long mod) {
    if (x == 0 || y == 0)
      return 0L;
    if (x >= mod || y >= mod || x * y >= mod) {
      return mod + m(x, mod) * m(y, mod) % mod;
    } else {
      return x * y % mod;
    }
  }

  public static long m(long x, long mod) {
    return x >= 2 * mod ? x % mod : x >= mod ? x - mod : x;
  }


  public static long totient(long n) {
    long tot = n;
    for (int p = 2; p * p <= n; p++) {
      int e = 0;
      while (n % p == 0) {
        n /= p;
        e++;
      }
      if (e > 0)
        tot = tot / p * (p - 1);
    }
    if (n > 1) {
      tot = tot / n * (n - 1);
    }
    return tot;
  }

  public static void main(String[] args) {
    new Thread(null, new Runnable() {
      @Override
      public void run() {
        long start = System.currentTimeMillis();
        String debug = args.length > 0 ? args[0] : null;
        if (debug != null) {
          try {
            is = java.nio.file.Files.newInputStream(java.nio.file.Paths.get(debug));
          } catch (Exception e) {
            throw new RuntimeException(e);
          }
        }
        reader = new java.io.BufferedReader(new java.io.InputStreamReader(is), 32768);
        solve();
        out.flush();
        tr((System.currentTimeMillis() - start) + "ms");
      }
    }, "", 64000000).start();
  }

  private static java.io.InputStream is = System.in;
  private static java.io.PrintWriter out = new java.io.PrintWriter(System.out);
  private static java.util.StringTokenizer tokenizer = null;
  private static java.io.BufferedReader reader;

  public static String next() {
    while (tokenizer == null || !tokenizer.hasMoreTokens()) {
      try {
        tokenizer = new java.util.StringTokenizer(reader.readLine());
      } catch (Exception e) {
        throw new RuntimeException(e);
      }
    }
    return tokenizer.nextToken();
  }

  private static double nd() {
    return Double.parseDouble(next());
  }

  private static long nl() {
    return Long.parseLong(next());
  }

  private static int[] na(int n) {
    int[] a = new int[n];
    for (int i = 0; i < n; i++)
      a[i] = ni();
    return a;
  }

  private static char[] ns() {
    return next().toCharArray();
  }

  private static long[] nal(int n) {
    long[] a = new long[n];
    for (int i = 0; i < n; i++)
      a[i] = nl();
    return a;
  }

  private static int[][] ntable(int n, int m) {
    int[][] table = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[i][j] = ni();
      }
    }
    return table;
  }

  private static int[][] nlist(int n, int m) {
    int[][] table = new int[m][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[j][i] = ni();
      }
    }
    return table;
  }

  private static int ni() {
    return Integer.parseInt(next());
  }

  private static void tr(Object... o) {
    if (is != System.in)
      System.out.println(java.util.Arrays.deepToString(o));
  }
}