Power Tower

题目来源

CF Round #454(Div 1) D

题目描述

有$n$个数$a_1, a_2, \dots, a_n$，$q$组询问。每次给一段区间$[l, r]$，你要计算$a_l^{a_{l+1} ^{\dots^{a_r}}} \bmod m$。

输入格式

第一行两个整数$n, m (1\leq n\leq 10^5, 1\leq m\leq 10^9)$。

接下来一行，一共$n$个整数$a_1, a_2, \dots, a_n (1\leq a_i\leq 10^9)$。

接下来一行一个整数$q(1\leq q\leq 10^5)$。接下来$q$行，每行两个整数$l, r(1\leq l \leq r \leq n)$。

输出格式

一共$q$行，每行一个数表示答案。

样例输入

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

样例输出

1
1
2
4
256
3
27
597484987