Жрецы культа Кетцалькоатля хотят построить величественную башню, символизирующую мощь их бога. Башня обычно строится из заряженных мощью камней. Она строится с помощью редкой магии, которая заставляет верхнюю часть башни левитировать над землёй, в то время как очередной камень пристраивается снизу башни. Если верхняя часть башни, построенная из k - 1 камней, обладает мощью p и мы хотим добавить к ней камень, заряженный мощью wk, то значение мощи новой башни будет равно {wk}p.
Камни добавляются, начиная с последнего и заканчивая нижним, поэтому для последовательности w1, ..., wm значение мощи будет равно
После того, как башня построена, её мощь может быть настолько колоссальной, что человеческий разум будет не в силах осознать её. Но жрецы всё ещё хотят иметь какую-то информацию о мощи башни, поэтому они хотят узнать значение приведённой мощи, которое равно истинному значению взятому по модулю m. У жрецов есть n камней пронумерованных от 1 до n. Они просят вас посчитать, каким значением приведённой мощи будет обладать башня, если её построить из камней с номерами l, l + 1, ..., r.
Первая строка ввода содержит два целых числа n (1 ≤ n ≤ 105) и m (1 ≤ m ≤ 109).
Вторая строка ввода содержит n целых чисел wk (1 ≤ wk ≤ 109), обозначающих значение мощи камней, имеющихся у жрецов.
Третья строка содержит единственное число q (1 ≤ q ≤ 105), равное числу вопросов, которые вам зададут жрецы.
kth из следующих q строк содержит два целых числа lk и rk (1 ≤ lk ≤ rk ≤ n).
Выведите q целых чисел. k-е из них должно быть равно величине приведённой мощи, которая будет у башни, построенной из камней с номерами lk, lk + 1, ..., rk.
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
327 = 7625597484987
