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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Iterator;
import java.io.BufferedWriter;
import java.util.Collection;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Jialin Ouyang (Jialin.Ouyang@gmail.com)
 */
public class Main {
  public static void main(String[] args) {
    InputStream inputStream = System.in;
    OutputStream outputStream = System.out;
    QuickScanner in = new QuickScanner(inputStream);
    QuickWriter out = new QuickWriter(outputStream);
    TaskD solver = new TaskD();
    solver.solve(1, in, out);
    out.close();
  }

  static class TaskD {
    int n;
    IntArrayList phis;
    int[] ws;

    public void solve(int testNumber, QuickScanner in, QuickWriter out) {
      n = in.nextInt();
      phis = calcPhis(in.nextInt());
      ws = in.nextInt(n);
      for (int remQuery = in.nextInt(); remQuery > 0; --remQuery) {
        int lower = in.nextInt() - 1;
        int upper = Math.min(in.nextInt(), lower + phis.size) - 1;
        out.println(calc(lower, upper));
      }
    }

    int calc(int lower, int upper) {
      int last = 1;
      for (int i = upper, j = upper - lower; i >= lower; --i, --j) {
        int phi = phis.get(j);
        last = IntModular.powPlus(ws[i], last, phi);
      }
      return last % phis.get(0);
    }

    IntArrayList calcPhis(int mod) {
      IntArrayList res = new IntArrayList(64);
      res.add(mod);
      while (res.peekLast() > 1) {
        res.add(IntUtils.phi(res.peekLast()));
      }
      return res;
    }

  }

  static interface IntCollection {
  }

  static class QuickWriter {
    private final PrintWriter writer;

    public QuickWriter(OutputStream outputStream) {
      this.writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

    public QuickWriter(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();
    }

  }

  static class IntArrayList implements Displayable, IntCollection, Iterable<Integer> {
    private static final int[] EMPTY = {};
    public int[] values;
    public int size;

    public IntArrayList() {
      values = EMPTY;
      clear();
    }

    public IntArrayList(int capacity) {
      values = new int[IntUtils.nextPow2(capacity)];
      clear();
    }

    public IntArrayList(Collection<Integer> collection) {
      this(collection.size());
      addAll(collection);
    }


    public void clear() {
      size = 0;
    }


    public void add(int value) {
      ensureCapacity(size + 1);
      addInternal(value);
    }


    public void addAll(Collection<Integer> values) {
      ensureCapacity(size + values.size());
      for (int value : values) {
        addInternal(value);
      }
    }

    public int peekLast() {
      return values[size - 1];
    }

    public int get(int idx) {
      if (idx >= size) throw new ArrayIndexOutOfBoundsException();
      return values[idx];
    }

    public void ensureCapacity(int capacity) {
      if (capacity <= values.length) return;
      int[] newValues = new int[IntUtils.nextPow2(capacity)];
      for (int i = 0; i < size; ++i) {
        newValues[i] = values[i];
      }
      values = newValues;
    }


    public Iterator<Integer> iterator() {
      return new Iterator<Integer>() {
        private int i = 0;


        public boolean hasNext() {
          return i < size;
        }


        public Integer next() {
          return values[i++];
        }
      };
    }

    private void addInternal(int value) {
      values[size++] = value;
    }

  }

  static class QuickScanner {
    private static final int BUFFER_SIZE = 1024;
    private InputStream stream;
    private byte[] buffer;
    private int currentPosition;
    private int numberOfChars;

    public QuickScanner(InputStream stream) {
      this.stream = stream;
      this.buffer = new byte[BUFFER_SIZE];
      this.currentPosition = 0;
      this.numberOfChars = 0;
    }

    public int nextInt() {
      int c = nextNonSpaceChar();
      boolean positive = true;
      if (c == '-') {
        positive = false;
        c = nextChar();
      }
      int res = 0;
      do {
        if (c < '0' || '9' < c) throw new RuntimeException();
        res = res * 10 + (c - '0');
        c = nextChar();
      } while (!isSpaceChar(c));
      return positive ? res : -res;
    }

    public int[] nextInt(int n) {
      int[] res = new int[n];
      nextInt(n, res);
      return res;
    }

    public void nextInt(int n, int[] res) {
      for (int i = 0; i < n; ++i) {
        res[i] = nextInt();
      }
    }

    public int nextNonSpaceChar() {
      int res = nextChar();
      for (; isSpaceChar(res) || res < 0; res = nextChar()) ;
      return res;
    }

    public int nextChar() {
      if (numberOfChars == -1) {
        throw new RuntimeException();
      }
      if (currentPosition >= numberOfChars) {
        currentPosition = 0;
        try {
          numberOfChars = stream.read(buffer);
        } catch (Exception e) {
          throw new RuntimeException(e);
        }
        if (numberOfChars <= 0) {
          return -1;
        }
      }
      return buffer[currentPosition++];
    }

    public boolean isSpaceChar(int c) {
      return c == ' ' || c == '\t' || isEndOfLineChar(c);
    }

    public boolean isEndOfLineChar(int c) {
      return c == '\n' || c == '\r' || c < 0;
    }

  }

  static interface Displayable {
  }

  static class IntUtils {
    public static boolean isPow2(int n) {
      return n > 0 && (n & (n - 1)) == 0;
    }

    public static int nextPow2(int n) {
      if (n < 1) return 1;
      return isPow2(n) ? n : Integer.highestOneBit(n) << 1;
    }

    public static int phi(int n) {
      int res = 1;
      for (int i = 2; i <= n / i; ++i)
        if (n % i == 0) {
          res *= i - 1;
          n /= i;
          for (; n % i == 0; res *= i, n /= i) {
          }
        }
      if (n > 1) res *= n - 1;
      return res;
    }

  }

  static class IntModular {
    private static final int MOD = 1000000007;
    public final int mod;
    private final int[] x;

    public IntModular() {
      this(MOD);
    }

    public IntModular(int mod) {
      this.mod = mod;
      this.x = new int[2];
    }

    public static int mul(int a, int b, int mod) {
      return a > 0
          ? (b < mod / a ? a * b : (int) ((long) a * b % mod))
          : 0;
    }

    public static int fix(int a, int mod) {
      a = slightFix(a, mod);
      return 0 <= a && a < mod ? a : slightFix(a % mod, mod);
    }

    public static int powPlus(int a, int b, int mod) {
      if (b == 0) return 1;
      int res = 1;
      boolean exceed = a >= mod;
      a = fix(a, mod);
      while (b > 0) {
        if ((b & 1) > 0) {
          exceed |= a > 0 && res >= mod / a;
          res = mul(res, a, mod);
        }
        b >>= 1;
        if (b > 0) {
          exceed |= a > 0 && a >= mod / a;
          a = mul(a, a, mod);
        }
      }
      return res + (exceed ? mod : 0);
    }

    private static int slightFix(int a, int mod) {
      return a >= mod
          ? a - mod
          : a < 0 ? a + mod : a;
    }

  }
}