【题目背景】

小奇总是在数学课上思考奇怪的问题。

【问题描述】

给定一个长度为n的数列，以及m次询问，每次给出三个数l，r和P，询问 (a[l'] + a[l'+1] + ... + a[r']) mod P的最小值。

其中l <= l' <= r' <= r。

即模意义下的区间子串和最小值。

【输入格式】seq.in

第一行包含两个正整数n和m，表示数列的长度和询问的个数。

第二行为n个整数，为a[1]..a[n]。

接下来m行，每行三个数l，r和P，代表一次询问。

【输出格式】seq.out

对于每次询问，输出一行一个整数表示要求的结果

【样例输入】

4 2
8 15 9 9
1 3 10
1 4 17

【样例输出】

2
1

【数据范围】

对于20%的数据 n<=100，m<=100，p<=200

对于40%的数据 n<=200，m<=1000，p<=500

对于70%的数据 n<=100000，m<=10000，p<=200

对于100%的数据 n<=500000，m<=10000，

p<=500，1<=a[i]<=10^9