Parity of Subarray Sums

You are given an array of N integers and Q queries. For each query, you are provided with two indices L and R (0-indexed). Your task is to determine whether the sum of the subarray from arr[L] to arr[R] is even or odd. Output Even if the sum is even, otherwise output Odd.

To solve this problem efficiently, consider using the prefix sum technique. Let \(\text{prefix}[i+1]=\text{prefix}[i]+\text{arr}[i]\) for \(0 \leq i < N\), then the sum of a subarray from L to R can be computed as \(\text{prefix}[R+1]-\text{prefix}[L]\).

Input and Output are handled via standard input and output (stdin and stdout).

inputFormat

The input is given in the following format:

N
arr[0] arr[1] ... arr[N-1]
Q
L1 R1
L2 R2
... 
LQ RQ

where:

• N is the number of elements in the array.
• The second line contains N space-separated integers.
• Q denotes the number of queries.
• Each of the next Q lines contains two integers L and R (0-indexed) representing a query.

outputFormat

For each query, output a single line containing either "Even" if the sum of the subarray is even, or "Odd" if it is odd.

## sample

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

Even
Odd
Even

</p>