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\)