题目背景

题目描述

给你一个长为 $n$ 的序列 $a$，有 $m$ 次查询，每次查询区间 $[l,r]$ 模 $k$ 意义下的最小值。

输入格式

第一行两个整数 $n,m$。

第二行 $n$ 个整数表示 $a$。

下面 $m$ 行，每行三个整数 $l,r,k$ 表示一次询问。

输出格式

对于每个查询操作，每行输出一个答案。

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

提示

Idea：mcyl35，Solution：mcyl35，Code：mcyl35，Data：cyffff&mcyl35

本题采用捆绑测试。

对于 $100\%$ 的数据，$1\le n,m\le3\times10^5$，$1\le a_i,k\le 10^5$。

前 $6$ 个 $\text{Subtask}$ 的空间限制为 $256\text{MB}$，第 $7$ 个 $\text{Subtask}$ 的空间限制为 $128\text{MB}$。