You are given an integer $n$ ($n \ge 0$) represented with $k$ digits in base (radix) $b$. So,
$$n = a_1 \cdot b^{k-1} + a_2 \cdot b^{k-2} + \ldots a_{k-1} \cdot b + a_k.$$
For example, if $b=17, k=3$ and $a=[11, 15, 7]$ then $n=11\cdot17^2+15\cdot17+7=3179+255+7=3441$.
Determine whether $n$ is even or odd.
Input
The first line contains two integers $b$ and $k$ ($2\le b\le 100$, $1\le k\le 10^5$) — the base of the number and the number of digits.
The second line contains $k$ integers $a_1, a_2, \ldots, a_k$ ($0\le a_i < b$) — the digits of $n$.
The representation of $n$ contains no unnecessary leading zero. That is, $a_1$ can be equal to $0$ only if $k = 1$.
Output
Print “even” if $n$ is even, otherwise print “odd”.
You can print each letter in any case (upper or lower).
Examples
input
13 3
3 2 7
output
even
input
10 9
1 2 3 4 5 6 7 8 9
output
odd
input
99 5
32 92 85 74 4
output
odd
input
2 2
1 0
output
even
Note
In the first example, $n = 3 \cdot 13^2 + 2 \cdot 13 + 7 = 540$, which is even.
In the second example, $n = 123456789$ is odd.
In the third example, $n = 32 \cdot 99^4 + 92 \cdot 99^3 + 85 \cdot 99^2 + 74 \cdot 99 + 4 = 3164015155$ is odd.
In the fourth example $n = 2$.
Solution:
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int b, k;
cin >> b >> k;
vector<int> a(k);
for (int i = 0; i < k; i++) {
cin >> a[i];
}
int p = 1, s = 0;
for (int i = k - 1; i >= 0; i--) {
s = (s + p * a[i]) % 2;
p = p * b % 2;
}
cout << (s ? "odd" : "even") << '\n';
return 0;
}
