因为Cocoa心算能力Max，所以店长叫她帮忙统计店里最近的数据。店长首先给出了一个长度为n的整数序列a。Cocoa第一个任务是计算出一个长度同样为n的整数序列b，b[1]=0，对于2<=i<=n，b[i]的值为使得公式|a[j]-a[i]|(1<=j<i)最小的a[j]，若有多个值满足要求，求出最小的那一个。接下来店长给出了一些询问，每个询问有三个正整数l,r,k，假设区间b[l]~b[r]内最大值与最小值的差为c,店长希望Cocoa能够求出有多少个k位非负整数（不含前导0，单独的0为1位数）的平方末尾为c。Cocoa认为这太麻烦了，于是便来请你帮忙。

输入文件第一行包含两个整数n,p，n表示序列的长度。

接下来第二行有n个整数：a[1],a[2],…,a[n]，表示序列a的值。

第三行包含了一个非负整数q，表示询问的个数。

接下来q行，每行包含三个正整数l，r，k，表示每一次的询问。

输出包含q行，对于每一个区间询问，单独输出一行整数，表示有多少数满足要求，答案对p取模。

[样例解释]

根据题意，求出的b数组为：[0,1,2,3,4]。

区间[1,3]内最大值为2，最小值为0，差为c=2。

没有满足要求的数。

区间[1,5]内最大值为4，最小值为0，差为c=4。

满足要求的数有

2^2=4,

8^2=64,

共两个。

另外一组样例：

[输入样例1]

7 2

3 3 3 3 3 3 3

2

1 2 2

4 7 2

[输出样例1]

0

1

[样例解释1]

根据题意，求出的b数组为：[0,3,3,3,3,3,3]。

区间[1,2]内最大值为3，最小值为0，差为3。

没有满足要求的数。

区间[4,7]内最大值为3，最小值为3，差为0。

满足要求的数有10,20,30,40,50,60,70,80,90,共9个（9%2=1）。

[数据范围及约定]

对于30%的数据满足

n<=1000，

q<=100,

1<=k<=3.

对于100%的数据满足

1<=n<=100000,

1<=p<=23333333,

0<=∀a[i]<=99,

0<=q<=50000,

1<=l<=r<=n,

1<=k<=10^13