Anxdada的询问(hard)

Anxdada提了一个问题, 他想考考fold:

给出一个长度为n(1≤n≤1000000)的数组a(下标从1开始), Anxdada有q(1≤q≤1000000)个询问, 对于每次询问: 他想知道数组a中下标在区间[l,r]中所有数字的乘积对固定数字p(1≤p≤1000000000)取余后的结果是多少?

由于这个问题太难了, fold回答不上来.

所以Anxdada简化了一下问题: 保证这次询问的区间[l,r]相比上一次询问(如果存在)的区间[l',r']都有1≤l'≤l≤n 且 1≤r'≤r≤n

这个问题依然很难, 你能帮帮fold解决这个问题吗?

由于输入数据量大, 推荐使用输入输出外挂: https://paste.ubuntu.com/p/4Gkh5THTvB/ (时限>标程2倍时间)

因为被大量线段树卡过去了，时间减少到6000ms,（我测了下，只要是正解，则80%的时间都在输入输出上，你写得常数再大对时间也没啥影响，除非你挫到写出6倍常数）

第一行有2个整数n(1≤n≤1000000)和p(1≤p≤1000000000), 含义如题面所述

第二行包含n个整数代表数组a中的元素(0≤a[i]≤1000000000)

第三行包含一个整数q(1≤q≤1000000), 代表询问的个数

接下来q行, 每一行包含2个整数l_i, r_i(1≤l_i≤r_i≤n), 代表Anxdada的询问区间是[l_i, r_i]

对于任意的1<i≤q, 都满足: 1≤l_i-1≤l_i≤n 且 1≤r_i-1≤r_i≤n

输出q行, 每一行一个非负整数表示询问的答案

3 7
1 2 3
2
1 2
2 3

2
6