Given two sequences filled with non-negative integers, and
, of length
, you will answer
queries, each consisting of two numbers,
and
. For each query, find a
where
that will minimize
and output the minimized value.
Constraints
For all subtasks:
Subtask 1 [20%]
Subtask 2 [80%]
No additional constraints.
Input Specification
The first line consists of two integers and
, the length of the sequences and the number of queries.
The next two lines consist of integers.
The following lines consist of two integers
and
.
Output Specification
Output the minimized value for each query on separate lines.
Sample Input
4 4
7 5 3 5
6 2 9 1
1 2
2 3
3 4
1 2
Sample Output
7
9
3
7
Comments