Statement
길이 의 정수 수열 이 주어진다.
당신은 개의 쿼리를 처리해야 한다. 각 쿼리는 두 정수 로 주어진다.
쿼리마다 정수 를 가 되도록 하나 고른다. 그 후 길이 의 정수 수열 를 고른다. 는 다음 조건을 만족해야 한다.
- 모든 에 대해 이다.
이때 의 최댓값을 출력하여라.
Input
첫째 줄에 두 정수 가 공백으로 구분되어 주어진다
둘째 줄에 개의 정수 이 공백으로 구분되어 주어진다.
다음 개의 줄에는 쿼리를 나타내는 두 정수 가 공백으로 구분되어 주어진다.
Output
각 쿼리마다 정답을 한 줄에 하나씩 출력한다.
Constraints
- 입력으로 주어지는 모든 수는 정수이다.
Subtasks
Samples
Sample 1
Input
4 4
5 3 10 8
1 4
2 4
1 2
3 4
Output
22
19
6
16
Sample 2
Input
3 3
-5 100 -1
1 3
2 3
3 3
Output
95
100
-1