Power Tower

Priests of the Quetzalcoatl 교단은 자신들의 신의 거듭제곱을 나타내는 탑을 건설하려 한다. 탑은 보통 힘이 충전된 바위로 만든다. 희귀한 마법으로 현재 탑의 꼭대기를 공중에 띄우고 그 아래에 바위를 추가하여 탑을 건설한다. k - 1개의 바위로 만들어진 꼭대기가 힘 p를 지니고 있고 힘 wk이 충전된 바위를 추가하려 한다면, 새 탑의 힘 값은 {wk}p가 된다.

바위는 마지막부터 처음 순서로 추가한다. 즉, 수열 w1, ..., wm에 대한 힘의 값은 다음과 같다.

탑을 완성한 뒤에는 그 힘이 극도로 클 수 있다. 하지만 사제들은 여전히 이에 관한 어떤 정보를 얻고 싶어 한다. 구체적으로는 힘의 실제 값을 m으로 나눈 나머지인 누적 힘이라는 수를 알고 싶어 한다. 사제들은 1부터 n까지 번호가 매겨진 n개의 바위를 가지고 있다. 그들은 번호가 l, l + 1, ..., r인 바위로 탑을 만들면 그 탑이 어떤 누적 힘 값을 지니는지 계산해 달라고 요청한다.

입력의 첫째 줄에 두 정수 n (1 ≤ n ≤ 105)와 m (1 ≤ m ≤ 109)가 주어진다.

입력의 둘째 줄에 사제들이 가진 바위의 힘을 나타내는 n개의 정수 wk (1 ≤ wk ≤ 109)이 주어진다.

입력의 셋째 줄에 사제들이 요청한 질의의 수인 정수 q (1 ≤ q ≤ 105)이 하나 주어진다.

이어지는 q개 줄 중 kth 줄에는 두 정수 lk와 rk (1 ≤ lk ≤ rk ≤ n)가 주어진다.

q개의 정수를 출력한다. 그중 k-th 정수는 바위 lk, lk + 1, ..., rk로 탑을 만들었을 때 탑이 지니는 누적 힘의 값이어야 한다.

327 = 7625597484987