You are given an integer array $A$ of size $N$. You are also given $Q$ queries. In each query, you are given three integers $L$, $R$, and $D$ respectively.

You are required to determine the length of the largest contiguous segment in the indices range $[L,R]$ of $A$ that forms an arithmetic progression with a common difference of $D$.

Note: The segment whose length is $1$ always forms an arithmetic progression of a common difference $D$.

Input format

• First line: Two space-separated integers $N$ and $Q$ respectively
• Second line: $N$ space-separated integers denoting elements of $A$
• Next $Q$ lines: Three space-separated integers $L$, $R$, and $D$ $(1 \le L \le R \le N)$ respectively

Output format

Print $Q$ lines representing the answer such as the $i^{th}$ line denotes the answer for the $i^{th}$ query.

Constraints

$1 \le N \le 200000$

$1 \le A_i \le 200000$

$-200000 \le D \le 200000$