408409: GYM103115 C chino with minimum

Chino has an array $$$a$$$ with $$$n$$$ elements. Now she prepares $$$m$$$ different arithmetic sequence. The first term of the i-th arithmetic sequence is $$$b_i[0]$$$, the tolerance is $$$k_i$$$, and the length of the sequence is exactly $$$n$$$.

The element of $$$a$$$ marked $$$x$$$ and $$$b$$$ marked $$$y$$$ with same position in respective array. The element in $$$c$$$ in Same position marked $$$z$$$. $$$z$$$ is equal to $$$y$$$ minus $$$x$$$. ( $$$c_i=\{b_i[0]-a[0],b_i[1]-a[1],...,b_i[n-1]-a[n-1]\}$$$)

For each array $$$c$$$, marked $$$Minimum_i$$$ is the minimum element in $$$c_i$$$.

That is $$$Minimum_i=min(c_i[0],c_i[1],...,c_i[n-1])$$$

Now Chino want to know for each different array $$$b_i$$$, what are the generated $$$Minimum_i$$$.

In the first line, input two integer n,m$$$(1 \leq n,m \leq 10^5)$$$ means the length of the array the numbers of arithmetic sequence.

In the next line, input n non-negative integers $$$a[i](0 \leq a[i] \leq 10^{12})$$$

In the next m lines, input two integers $$$b_i[0],k_i(0 \leq b_i[0] \leq 10^{12}, -10^7 \leq k_i \leq 10^7)$$$

Output m lines, Represents each $$$Minimum_i$$$

5 3
1 9 2 4 3
10 -1
1 100
403 -100

0
0
0

$$$b_1=\{10,9,8,7,6\},c_1= \{9,0,6,3,3\}$$$,The minimum value is 0

$$$b_2=\{1,101,201,301,401\},c_2= \{0,92,199,297,398\}$$$,The minimum value is 0

$$$b_3=\{403,303,203,103,3\},c_3= \{401,294,201,99,0\}$$$,The minimum value is 0