Description

You are given a sequence $a$ of length $n$. There are $m$ queries. For each query, you need to find the minimum value in the interval $[l,r]$ under modulo $k$, i.e., $\min\{a_i \bmod k \mid l \le i \le r\}$.

Input Format

The first line contains two integers $n,m$.

The second line contains $n$ integers representing $a$.

The next $m$ lines each contain three integers $l,r,k$, representing one query.

Output Format

For each query, output one answer per line.

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

Hint

Idea: mcyl35, Solution: mcyl35, Code: mcyl35, Data: cyffff & mcyl35.

This problem uses bundled testdata.

Constraints: for $100\%$ of the testdata, $1\le n,m\le3\times10^5$, $1\le a_i,k\le 10^5$.

The memory limit for the first $6$ subtasks is $256\text{MB}$, and the memory limit for the $7$th subtask is $128\text{MB}$.

Translated by ChatGPT 5