【题目描述】
提示:我们在题目描述的最后一段提供了一份简要的、形式化描述的题面。
在遥远的未来，物理学家终于发现了时间和因果的自然规律。即使在一个人出生前，我们也可以通过理论分 析知晓他或她人生的一些信息，换言之，物理学允许我们从一定程度上"预言”一个人的"命运"。
简单来说，一个人小X的命运是一个由时间点构成的序列A:序列的第一个数代表着出生，而最后一个数代 表着死亡。每个节点u都有一个后继节点u＋1，表示这个人在u所代表的时间点做出的选择可以导向 u＋1。形式化的，一个选择就是两个相邻位置u,u+1。
一个人小X的一生是从出生(即第一个数)到死亡(即最后一个数）的一个序列，这个序列上任何一个包含 至少一个点的子区间都是这个人的一段人生经历，而他或她以所有可能的方式度过一生，从而拥有的所有 人生经历，都被称为潜在的人生经历。换言之，所有潜在的人生经历就是所有l到r的区间，满足 1<=l<=r≤n。在数学上，这样一个潜在的人生经历被记作有序对(l,r)，序列A所有潜在的人生经历的 集合记作$P_A$. 物理理论不仅允许我们观测代表命运的序列，还能让我们分析一些潜在的人生经历是否是“重要"的。一个人 小X所作出的每一个选择——即相邻的两个点——都可能是重要或不重要的。一段潜在的人生经历是否 重要，我们用这段经历中$a_i \  mod \  k$的最小值来衡量，我们称之为重要度。我们可以观测到一些潜在的人 生经历是重要的:换言之，我们可以观测得到一个数ai，满足$a_i \  mod \  k$是这段潜在的人生经历(l,r)中 $a_i \  mod \  k$(l≤j≤r)最小的。 序列A的数值早已被计算确定，一个人小X命运的不确定性已经大大降低了。但不确定性仍然是巨大的 ——来计算一下吧，对于给定的序列A和若干个区间[l，r]，找到(1,r)这段潜在的人生经历的重要度。
形式化的:给定一个长度为n的序列A，m次询问，每次给定l、r和k，求$\min_{i=l}^r \{ a_i \mod k \} $
【输入格式】
从文件 destiny.in中读入数据。
第一行两个整数n，m.
第二行n个整数表示序列A。
第3～ m＋2行，每行三个整数l，r，k，表示一次询问。
输入数据规模和限制参见本题末尾的表格。
【输出格式】
输出到文件destiny.out中。
输出共m行，每行一个整数，表示这次查询的答案。
【样例 1 输入】

10 10
15 14 14 4 8 10 18 14 10 9 
2 10 8
2 4 7
3 9 6
1 7 5
3 4 6
6 6 12
4 8 20
1 6 18
7 8 8
2 6 6

0
0
0
0
2
10
4
4
2
2

5 5
77 24 80 90 92 
2 3 84
4 5 37
1 1 4
3 5 85
1 4 46

24
16
1
5
24