Another Random Contest 1 P2 - Two Sequences

View as PDF

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

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.

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