题目背景

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

问题描述

给定一个长度为\(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\)