Maximum Element in Concatenated Array Queries

You are given two arrays (A) and (B) of length (n) each. First, construct a new array (C) by concatenating (A) and (B) (i.e. (C = A \Vert B)). Then, you will be given (q) queries. Each query consists of two indices (l) and (r) (0-indexed) that specify a subarray (C[l \ldots r]). Your task is to find the maximum element in that subarray for each query.

Formally, given: [ C = [A_0, A_1, \ldots, A_{n-1}, B_0, B_1, \ldots, B_{n-1}], ] and a query ((l, r)) where (0 \le l \le r < 2n), determine: [ \max_{l \le i \le r} C_i. ]

inputFormat

The first line contains two integers (n) and (q) separated by a space, where (n) is the length of each array and (q) is the number of queries. The second line contains (n) integers representing array (A). The third line contains (n) integers representing array (B). Each of the next (q) lines contains two integers (l) and (r), representing a query on the concatenated array (C).

outputFormat

For each query, output the maximum element in the specified subarray of (C) on a new line.## sample

3 2
4 3 5
1 2 7
1 4
0 5

5
7