题目背景

点我进入原题面

题目描述

给定 $n$ 个数 $w_1,W_2,\cdots,w_n$ 与模数 $m$。

给出 $q$ 组询问，每次给出一个区间 $l\sim r$，你需要求出这个区间的幂塔对 $m$ 取余的结果。

区间幂塔指的是

$$w_l^{w_{l+1}^{w_{l+2}^{w_{l+3}^{\cdots}}}} \bmod m $$

输入格式

第一行输入 $n$ 和 $m$。

第二行输入 $w_1,w_2,\cdots,w_n$。

第三行输入一个整数 $q$。

接下来 $q$ 行每行输入两个整数 $l,r$。

输出格式

输出一共输出 $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

提示

• $1\leq n,q\leq 10^5,1\leq m\leq 10^9$
• $1\leq w_i\leq 10^9$
• $1\leq l_i\leq r_i\leq n$