Array Increment and Maximum Query

You are given an array \(a_1, a_2, \dots, a_N\) of integers and \(M\) operations. Each operation is defined by two indices \(L\) and \(R\) (1-indexed) and increments each element in the subarray \(a_L, a_{L+1}, \dots, a_R\) by \(1\). After performing all \(M\) operations, you are asked to answer \(Q\) queries. Each query is specified by two indices \(L\) and \(R\), and you must output the maximum value among the elements in the subarray \(a_L, a_{L+1}, \dots, a_R\) after all operations have been applied.

Formally, for an operation with parameters \(L\) and \(R\), for every index \(i\) such that \(L \le i \le R\), the array is updated as follows:

[ a_i = a_i + 1 ]

After processing all operations, for a query with parameters \(L\) and \(R\), you need to compute:

[ \max_{L \le i \le R} a_i ]

Input/Output: The input will be given via standard input and the output should be printed to standard output.

inputFormat

The input begins with two integers \(N\) and \(M\), representing the size of the array and the number of operations, respectively.

The next line contains \(N\) space-separated integers, representing the initial array \(a_1, a_2, \dots, a_N\).

This is followed by \(M\) lines, each containing two integers \(L\) and \(R\), describing an operation.

The next line contains an integer \(Q\), the number of queries.

Then \(Q\) lines follow, each containing two integers \(L\) and \(R\), describing a query.

outputFormat

Output \(Q\) lines, each containing a single integer: the answer to each query (the maximum value in the subarray specified by the query) after all operations have been applied.

## sample

5 3
1 2 3 4 5
1 3
2 5
1 4
2
1 3
2 5

6
6

</p>