题目描述

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

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

输入格式

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

第二行为$\red{n}$个整数，为$\red{a[1]..a[n]}$。

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

输出格式

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

样例

输入样例

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

输出样例

2
1

提示

对于$\red{20\%}$的数据 $\red{n<=100，}$$\red{m<=100，}$$\red{p<=200}$

对于$\red{40\%}$的数据 $\red{n<=200，}$$\red{m<=1000，}$$\red{p<=500}$

对于$\red{70\%}$的数据 $\red{n<=100000，}$$\red{m<=10000，}$$\red{p<=200}$

对于$\red{100\%}$的数据 $\red{n<=500000，}$$\red{m<=10000，}$$\red{p<=500，}$$\red{1<=a[i]<=10^9}$