See the original problem on HackerRank.
You are given an array of integers A and you will be asked to answer some queries.
Each query is in the form:


And you have to return the sum of absolute values from A[i]
to A[j]
, that is:


Input Format
First Line of Input contains N and Q separated by space. Next Line contains N space separated integers. Next Q queries follows, each query contains two integers i and j separated by a space.
Constraints


Output Format
For each query output Even if the value is even, otherwise Odd.
Example
Input:


Output:


Explanation:
Query 1 : abs(abs(abs(5) + 1) + 2) = 8 => Even
Query 3 : abs(abs(abs(8) + (8)) + (8)) = 8 => Even
Query 4 : abs(abs(8)+4) = 12 => Even
Query 5 : abs(abs(abs(5) + 8 )+(5)) =>8 => Even
Solutions
This is a typical use case for prefix sum. We calculate the running sum of all the elements and we answer the queries just by applying the prefix sum formula:
\( sum_i_j = PrefixSum[j]  PrefixSum[i1] \)
That is, the sum between indexes \(i\) and \(j\) (inclusive) is calculated as the difference between the prefix sum at index \(\j) and the prefix sum at index \(i1\).
Two notes:
 the prefix sum is not simply calculated with addition because absolute value is applied on top.
 in the code below, remember the indxing is 0based
Here is an implementation of the presented idea in C++:

