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개 줄 중 lk번째 줄에는 두 정수 rk (1 ≤ lk ≤ rk ≤ n)이 주어진다.

q개의 정수를 출력한다. 그중 k-th번째 정수는 번호가 lk, lk + 1, ..., rk인 바위로 탑을 만들었을 때 탑이 갖게 될 누적 위력의 값이어야 한다.

327 = 7625597484987