# Power Tower

## 题意翻译

### 题目描述
给定 $n$ 个数 $w_1,w_2,...,w_n$ 与模数 $m$。
给出 $q$ 组询问，每次询问给出 $l,r$，求 $w_l^{w_{l+1}^{{...}^{w_r}}} \mod m$ 的值。
$1\leq n,q \leq 10^5,1\leq m,w_k\leq10^9$。
### 输入格式
第一行两个整数 $n,m$。
接下来一行 $n$ 个整数 $w_1,w_2,...,w_n$。
接下来一行 $1$ 个整数 $q$。
接下来 $q$ 行，每行两个整数 $l,r$ 表示一组询问。

## 题目描述

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 $ w_{k} $ then value of power of a new tower will be $ {w_{k}}^{p} $ .
Rocks are added from the last to the first. That is for sequence $ w_{1},...,w_{m} $ value of power will be
![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF906D/a7b9adfbee151f2e3ef09f9dbad2cf6b657882ca.png)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 $ .

## 输入输出格式

### 输入格式

First line of input contains two integers $ n $ ( $ 1<=n<=10^{5} $ ) and $ m $ ( $ 1<=m<=10^{9} $ ).
Second line of input contains $ n $ integers $ w_{k} $ ( $ 1<=w_{k}<=10^{9} $ ) which is the power of rocks that priests have.
Third line of input contains single integer $ q $ ( $ 1<=q<=10^{5} $ ) which is amount of queries from priests to you.
$ k^{th} $ of next $ q $ lines contains two integers $ l_{k} $ and $ r_{k} $ ( $ 1<=l_{k}<=r_{k}<=n $ ).

### 输出格式

Output $ q $ integers. $ k $ -th of them must be the amount of cumulative power the tower will have if is built from rocks $ l_{k},l_{k}+1,...,r_{k} $ .

## 输入输出样例

### 输入样例 #1

```
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
1
2
4
256
3
27
597484987
```

## 说明

$ 3^{27}=7625597484987 $