题目背景

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

问题描述

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

其中$l<=l'<=r'<=r$

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

输入格式

第一行包含两个正整数$n$和$m$，表示数列的长度和询问的个数。
第二行为n个整数，为$a[1]..a[n]$。
接下来m行，每行三个数$l$，$r$和$P$，代表一次询问。

输出格式

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

样例输入

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$