Power Tower

Problem Source

Codeforces Round #454 (Div. 1) D

Problem Description

You are given $n$ numbers $a_1, a_2, \dots, a_n$ and $q$ queries. For each query, given an interval $[l, r]$, you must compute $a_l^{a_{l+1} ^{\dots^{a_r}}} \bmod m$.

Input Format

The first line contains two integers $n, m$ ($1 \leq n \leq 10^5$, $1 \leq m \leq 10^9$).

The next line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq 10^9$).

The next line contains an integer $q$ ($1 \leq q \leq 10^5$). The following $q$ lines each contain two integers $l, r$ ($1 \leq l \leq r \leq n$).

Output Format

Output $q$ lines, each containing one number: the answer for that query.

Sample 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

Sample Output

1
1
2
4
256
3
27
597484987