You are given an array\(A\) of size \(N\) and \(Q\) queries. For each query, you are given two indices of the array \(L\) and \(R\). The subarray generated from \(L\) to \(R\) is reversed. Your task is to determine the maximum sum of the subarrays.

Note: After each query is solved, the array comes to its initial states.

Input format

• First line: Two space-separated integers \(N\) and \(Q\)
• Next line: \(N\) space-separated integers denoting the array elements.
• Next \(Q\) lines: Two space-separated integers in every line denoting the values of \(L_i\)and \(R_i\)

Output format

For each query, print the required answer in a new line.

Constraints

• \(1 \leq N,Q \leq 10^5\)
• \(1 \leq L \leq R \leq N\)
• \(-10^6 \leq A_i \leq 10^6\)