Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Is Bita Happy?

By shefin · Limits 1s, 512 MB

Bita has learned bitwise-operations recently. She is doing some experiments with these operations now. Whenever she becomes happy, she frees doves. At this moment, she becomes happy when the following equation becomes correct for some integers a, b and k: (a & b) & (1 << k) ≠ 0

where ‘&’ is bitwise AND operator, ‘<<’ is bitwise left-shift operator.

You’ll be given a, k, L and R. Find out the values of b in the range [L, R] for which Bita becomes happy. Calculate the summation of those b values. If Bita never becomes happy, the summation is 0. Since Bita dislikes printed numbers, you have to tell whether this summation is odd or even.

Input

Input will start with an integer T, the number of test cases. In each test case, there will be 4 integers a, k, L, R in a line.

Constraints:
1 <= T <= 105
1 <= a, L, R <= 109
0 <= k <= 30
L <= R


Output

For each test case, if the summation described in the statement is odd, print “Odd”, otherwise print “Even” in a single line.

Sample

InputOutput
2
5 2 1 6
5 0 14 17
Odd
Even


In the first case, the valid values of b are 4, 5, 6. The summation is: (4+5+6) = 15, which is odd.

In the second case, the valid values of b are 15, 17. The summation is: (15 + 17) = 32, which is even.


Notes:

  1. The ‘&’ (bitwise AND) operator takes two numbers as operands and does AND on every bit of two numbers. The result of AND is 1 only if both bits are 1, otherwise the result of AND is 0. For example, (16 & 11) = 12. It will be understandable if the numbers are converted to binary: (1110(2) & 1011(2) ) = 1010(2)

  2. The ‘<<’ (bitwise left-shift operator) takes two numbers, left shifts the bits of the first operand, the second operand decides the number of places to shift. For example, (1 << 3) = 8. Because, the binary form of 1 is 1(2) and after shifting it 3 places to left, it will be 1000(2), which is 8 in decimal.


Discussion
Statistics

52% Solution Ratio

mepromeeEarliest, 1w ago

mepromeeFastest, 0.0s

snow_manLightest, 524 kB

Wojciech.324122Shortest, 873B

Submit

Login to submit