Maximum Arithmetic Progression Length in Subarray

You are given a sequence of length $n$ and $m$ queries. For each query with parameters $l$, $r$, and $b$, you need to determine the maximum integer $x$ such that there exists an integer $a$ with $0 \le a < b$ for which the arithmetic progression $$a,; a+b,; a+2b,; \ldots,; a+(x-1)b$$ appears at least once in the subarray of the given sequence from index $l$ to $r$ (inclusive). If none of the numbers in the range $[0, b-1]$ appear in the subarray, output $0$.

Note: All indices are 1-indexed.

inputFormat

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 10^5$).

The second line contains $n$ integers representing the sequence.

Each of the next $m$ lines contains three integers $l$, $r$, and $b$, representing a query. It is guaranteed that $1 \le l \le r \le n$.

outputFormat

For each query, output a single integer: the maximum value of $x$ satisfying the condition described.

sample

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

3
0
2