#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
const int M = 1e9 + 7;
const int MOD = 998244353;
const double PI = 3.141592653589793238460;
long long int power(long long int a, long long int b) {
  long long int res = 1;
  if (a == 0) return 0;
  if (a == 1) return 1;
  for (; b > 0; b >>= 1) {
    if (b & 1) res = (res * a);
    if (res > MOD) res %= MOD;
    a = (a * a);
    if (a > MOD) a = a % MOD;
  }
  return res;
}
bool isPrime[1000100];
vector<int> prime;
void seive() {
  isPrime[0] = isPrime[1] = 1;
  for (int i = 2; i * i <= 1000000; i++) {
    if (!isPrime[i])
      for (int j = i * i; j <= 1000000; j += i) {
        isPrime[j] = 1;
      }
  }
  for (int i = 2; i <= 1000000; i++)
    if (!isPrime[i]) prime.push_back(i);
}
bool isPalindrome(string &temp) {
  int mid = temp.length() / 2;
  mid++;
  int j;
  int n = temp.length();
  for (int i = 0, j = n - 1; i < n && j >= 0; i++, j--) {
    if (temp[i] != temp[j]) return false;
  }
  return true;
}
int getbalance(string s) {
  int o = 0, c = 0, n = s.length();
  for (int i = 0; i < n; i++) {
    if (s[i] == '(')
      o++;
    else
      c++;
    if (c > o) return (-1);
  }
  return (o - c);
}
int getSum(int BITree[], int index) {
  int sum = 0;
  while (index > 0) {
    sum += BITree[index];
    index -= index & (-index);
  }
  return sum;
}
void updateBIT(int BITree[], int n, int index, int val) {
  while (index <= n) {
    BITree[index] += val;
    index += index & (-index);
  }
}
int getInvCount(int arr[], int n) {
  int invcount = 0;
  int BIT[n + 1];
  for (int i = 1; i <= n; i++) BIT[i] = 0;
  for (int i = n - 1; i >= 0; i--) {
    invcount += getSum(BIT, arr[i] - 1);
    updateBIT(BIT, n, arr[i], 1);
  }
  return invcount;
}
int main() {
  int tt = 1;
  while (tt--) {
    int n, m;
    cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++) cin >> arr[i];
    int inv = 0;
    for (int i = 0; i < n; i++)
      for (int j = i + 1; j < n; j++)
        if (arr[i] > arr[j]) inv++;
    bool flag = 0;
    if (inv % 2 == 0) flag = 1;
    cin >> m;
    for (int i = 0; i < m; i++) {
      int l, r;
      cin >> l >> r;
      int x = (r - l + 1) / 2;
      if (x % 2 == 1) flag = !flag;
      if (flag)
        cout << "even"
             << "\n";
      else
        cout << "odd"
             << "\n";
    }
  }
}

### Prompt

Please provide a cpp coded solution to the problem described below:

A permutation of size n is an array of size n such that each integer from 1 to n occurs exactly once in this array. An inversion in a permutation p is a pair of indices (i, j) such that i > j and ai < aj. For example, a permutation [4, 1, 3, 2] contains 4 inversions: (2, 1), (3, 1), (4, 1), (4, 3).

You are given a permutation a of size n and m queries to it. Each query is represented by two indices l and r denoting that you have to reverse the segment [l, r] of the permutation. For example, if a = [1, 2, 3, 4] and a query l = 2, r = 4 is applied, then the resulting permutation is [1, 4, 3, 2].

After each query you have to determine whether the number of inversions is odd or even.

Input

The first line contains one integer n (1 ≤ n ≤ 1500) — the size of the permutation. 

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ n) — the elements of the permutation. These integers are pairwise distinct.

The third line contains one integer m (1 ≤ m ≤ 2·105) — the number of queries to process.

Then m lines follow, i-th line containing two integers li, ri (1 ≤ li ≤ ri ≤ n) denoting that i-th query is to reverse a segment [li, ri] of the permutation. All queries are performed one after another.

Output

Print m lines. i-th of them must be equal to odd if the number of inversions in the permutation after i-th query is odd, and even otherwise.

Examples

Input

3
1 2 3
2
1 2
2 3


Output

odd
even


Input

4
1 2 4 3
4
1 1
1 4
1 4
2 3


Output

odd
odd
odd
even

Note

The first example:

  1. after the first query a = [2, 1, 3], inversion: (2, 1); 
  2. after the second query a = [2, 3, 1], inversions: (3, 1), (3, 2). 



The second example:

  1. a = [1, 2, 4, 3], inversion: (4, 3); 
  2. a = [3, 4, 2, 1], inversions: (3, 1), (4, 1), (3, 2), (4, 2), (4, 3); 
  3. a = [1, 2, 4, 3], inversion: (4, 3); 
  4. a = [1, 4, 2, 3], inversions: (3, 2), (4, 2). 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
const int M = 1e9 + 7;
const int MOD = 998244353;
const double PI = 3.141592653589793238460;
long long int power(long long int a, long long int b) {
  long long int res = 1;
  if (a == 0) return 0;
  if (a == 1) return 1;
  for (; b > 0; b >>= 1) {
    if (b & 1) res = (res * a);
    if (res > MOD) res %= MOD;
    a = (a * a);
    if (a > MOD) a = a % MOD;
  }
  return res;
}
bool isPrime[1000100];
vector<int> prime;
void seive() {
  isPrime[0] = isPrime[1] = 1;
  for (int i = 2; i * i <= 1000000; i++) {
    if (!isPrime[i])
      for (int j = i * i; j <= 1000000; j += i) {
        isPrime[j] = 1;
      }
  }
  for (int i = 2; i <= 1000000; i++)
    if (!isPrime[i]) prime.push_back(i);
}
bool isPalindrome(string &temp) {
  int mid = temp.length() / 2;
  mid++;
  int j;
  int n = temp.length();
  for (int i = 0, j = n - 1; i < n && j >= 0; i++, j--) {
    if (temp[i] != temp[j]) return false;
  }
  return true;
}
int getbalance(string s) {
  int o = 0, c = 0, n = s.length();
  for (int i = 0; i < n; i++) {
    if (s[i] == '(')
      o++;
    else
      c++;
    if (c > o) return (-1);
  }
  return (o - c);
}
int getSum(int BITree[], int index) {
  int sum = 0;
  while (index > 0) {
    sum += BITree[index];
    index -= index & (-index);
  }
  return sum;
}
void updateBIT(int BITree[], int n, int index, int val) {
  while (index <= n) {
    BITree[index] += val;
    index += index & (-index);
  }
}
int getInvCount(int arr[], int n) {
  int invcount = 0;
  int BIT[n + 1];
  for (int i = 1; i <= n; i++) BIT[i] = 0;
  for (int i = n - 1; i >= 0; i--) {
    invcount += getSum(BIT, arr[i] - 1);
    updateBIT(BIT, n, arr[i], 1);
  }
  return invcount;
}
int main() {
  int tt = 1;
  while (tt--) {
    int n, m;
    cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++) cin >> arr[i];
    int inv = 0;
    for (int i = 0; i < n; i++)
      for (int j = i + 1; j < n; j++)
        if (arr[i] > arr[j]) inv++;
    bool flag = 0;
    if (inv % 2 == 0) flag = 1;
    cin >> m;
    for (int i = 0; i < m; i++) {
      int l, r;
      cin >> l >> r;
      int x = (r - l + 1) / 2;
      if (x % 2 == 1) flag = !flag;
      if (flag)
        cout << "even"
             << "\n";
      else
        cout << "odd"
             << "\n";
    }
  }
}

```