养花

flower.cpp/in/out

• 时间限制：1s
• 内存限制：512MB

题目描述

小 C 在家种了 $n$ 盆花，每盆花有一个艳丽度 $a_i$。

在接下来的 $m$ 天中，每天早晨他会从一段编号连续的花中选择一盆摆放在客厅，并在晚上放回。同时每天有特定的光照强度 $k_i$，如果这一天里摆放在客厅的花艳丽度为 $x$，则他能获得的喜悦度为 $x \bmod k_i$。

他希望知道，每一天他能获得的最大喜悦度是多少。

输入格式

数据第一行包含两个正整数 $n, m$。

接下来一行 $n$ 个正整数，第 $i$ 个数 $a_i$ 表示第 $i$ 盆花的艳丽度。

接下来 $m$ 行，每行三个正整数 $l_i, r_i, k_i$，表示选花区间和光照强度。

输出格式

输出 $m$ 行，每行一个整数，表示最大喜悦度。

样例输入

5 5
1 2 3 4 5
1 3 2
1 3 3
1 4 4
5 5 5
3 5 3

样例输出

1
2
3
0
2

数据范围

• 对于 20% 的数据，$n, m \le 4000$。
• 对于 40% 的数据，$n, m \le 50000$。
• 对于另外 20% 的数据，$a_i \le 300$。
• 对于 100% 的数据，$n, m, a_i, k_i \le 10^5$。