Chino has an array a with  elements. Now she prepares  different arithmetic sequence. The first term of the  arithmetic sequence is , the tolerance is , and the length of the sequence is exactly .

The element of  marked and marked with same position in respective array. The element in in Same position marked . is equal to minus . ( )

For each array , marked is the minimum element in .

That is

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

In the first line, input two integer  means the length of the array the numbers of arithmetic sequence.

In the next line, input  non-negative integers 

In the next  lines, input two integers 

Output  lines, Represents each .

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

0
0
0

,The minimum value is 

,The minimum value is 

,The minimum value is