Minimum Modulo Value in Subarray Queries

Given an array a of length \( n \) and \( m \) queries, each query specifies an interval \( [l, r] \). For each query, compute the minimum value of \( a_i \bmod k \) for all indices \( i \) in the interval \( [l, r] \).

Note: The modulo operation is defined as the remainder when dividing by \( k \). All formulas are formatted in \( \LaTeX \).

inputFormat

The first line contains three integers \( n \), \( m \), and \( k \). The second line contains \( n \) space-separated integers representing the array a. Each of the following \( m \) lines contains two integers \( l \) and \( r \) which denote a query interval.

outputFormat

For each query, output a single integer on a new line, which is the minimum value of \( a_i \bmod k \) for \( i \) in \( [l, r] \).

sample

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

0
0
1