게임 예측

Sunset과 Elephant가 수열 $b_1, b_2, \ldots, b_m$에서 게임을 한다. 두 사람은 번갈아 움직이며 Sunset이 먼저 시작한다. 각 차례에서 현재 차례인 사람은 수열의 맨 앞이나 맨 뒤에 있는 값을 하나 골라 자신의 점수에 더하고 그 값을 수열에서 제거한다. 수열이 비면 게임이 끝난다. 두 사람은 모두 자신의 점수를 최대로 만들고자 하며 최선의 전략으로 게임을 한다.

수열 $a_1, a_2, \ldots, a_n$과 $q$개의 질의가 주어진다. $i$번째 질의에서는 두 정수 $l_i$와 $r_i$가 주어진다.

$b$의 초기 상태를 $a_{l_i}, a_{l_i+1}, \ldots, a_{r_i}$로 두었을 때 게임의 최종 결과를 구하는 프로그램을 작성하라. 이때 $m = r_i - l_i + 1$이고, $1 \le j \le m$인 모든 $j$에 대해 $b_j = a_{l_i+j-1}$이다.

각 테스트에는 테스트 케이스가 하나만 주어진다.

테스트 케이스의 첫 줄에는 수열의 길이와 질의의 수를 나타내는 두 정수 $n$과 $q$가 주어진다. ($1 \le n \le 100\,000$, $1 \le q \le 200\,000$)

둘째 줄에는 $n$개의 정수 $a_1, a_2, \ldots, a_n$이 주어진다. ($1 \le a_i \le 10^9$)

다음 $q$개의 줄에는 각각 질의를 나타내는 두 정수 $l_i$와 $r_i$가 주어진다. ($1 \le l_i \le r_i \le n$)

모든 $a_i$의 값은 $[1, 10^9]$ 범위의 정수 중에서 균등한 확률로 무작위로 선택된다. 이 무작위성 조건은 예제 테스트 케이스에는 적용되지 않지만, 제출한 풀이는 예제도 통과해야 한다.

각 질의마다 Sunset의 최종 점수 $S$와 Elephant의 최종 점수 $E$를 한 줄에 두 정수로 출력한다.