幂塔

时间限制：$1s$

空间限制：$256MB$

题目描述

给定一个长度为$n$的数列$\{w_i\}$，定义区间$[l,r]$的价值为${{{{w_l}^{w_{l+1}}}^{w_{l+2}}}^{...}}^{w_r}$，给出$q$次询问，每次询问给出$l,r$，你需要回答区间$[l,r]$的价值。答案对$m$取模。

初始设val为一 每次取出区间末尾的数x ，val变为 $x^{val}$ 直至取完区间内所有数，最终val即为区间价值。

数据格式

输入

第一行包含三个整数 $n,m,q$，其中 $q$ 表示询问数量。

第二行包含 $n$个整数 $w_i$。

接下来 $q$行每行给出 $l_k$和$r_k$。

输出

输出 $q$ 行整数表示每次询问的答案。

样例

输入1

10 1000000000 10
1 1 2 2 3 3 4 4 5 5
1 1
1 2
2 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10

输出1

1
1
1
1
256
816787456
41579008
215851008
814963203
581363203

数据范围及约定

$1≤n≤10^5,1≤m≤10^9,1≤w≤10^9,1≤q≤10^5$