Earliest Bus Departure

You are given n bus routes and m queries. Each bus route has a fixed frequency f that represents the time interval between consecutive bus departures. Specifically, for a bus route with frequency f, the departure times are given by \( f, 2f, 3f, \dots \).

For each query, you are provided with a bus route identifier \( r \) and a starting time \( T \). Your task is to compute the earliest departure time for the selected bus route which is greater than or equal to \( T \). In mathematical terms, if \( T \) is a multiple of \( f \) then the answer is \( T \); otherwise, it is \( f \times \left( \left\lfloor \frac{T}{f} \right\rfloor + 1 \right) \).

Output the answer for each query on a new line.

inputFormat

The first line contains two integers n and m (1 ≤ n, m ≤ 10⁵), representing the number of bus routes and the number of queries, respectively.

The second line contains n space-separated integers, where the i-th integer \( f_i \) (1 ≤ f_i ≤ 10⁹) denotes the frequency of the i-th bus route.

Each of the following m lines contains two space-separated integers: a route identifier \( r \) (1 ≤ r ≤ n) and the starting time \( T \) (1 ≤ T ≤ 10⁹).

outputFormat

For each query, output a single integer representing the earliest departure time of the bus on the specified route that is greater than or equal to the given starting time. Each output should be on its own line.

## sample

3 4
5 10 20
1 3
2 15
3 25
1 7

5
20
40
10

</p>