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