King Stone Bridge Game

Time limit1sMemory limit256 MB

Summary

Two kings alternate moving their own stones on N single-cell-row bridges, and the task is to name the winner under optimal play.

Level: Medium7 of 10
Topics: Game theory, Math
Solved: No attempts yet

Problem

Whiteking and Blackking want to play a stone game on single-log bridges. The game uses $N$ bridges. The $i$ -th bridge is a row of $A_i$ cells. At the start, a white stone is placed on the first cell of every bridge, and a black stone is placed on the last cell of every bridge.

On each turn, a king must move one stone of their own color. A stone moves to another cell on the same bridge. It cannot jump over an opponent's stone, and it cannot stay on its current cell. As long as these rules hold, a stone may move in either direction, including away from the opposing stone. The kings take turns. A king who cannot move any stone on their turn loses.

If both kings play optimally, predict who wins.

Input

The first line contains $N$ , the number of bridges.

The second line contains $A_1, A_2, A_3, \ldots, A_N$ , the number of cells on each bridge.

The third line contains the name of the king who moves first.

Output

Print the name of the winning king. The name always starts with a capital letter.

Constraints

$1 \le N \le 100{,}000$
$2 \le A_i \le 10^9$

Hint

Suppose a bridge has 6 cells, the white stone is on cell 3, and the black stone is on cell 5. The white stone can move to cell 1, 2, or 4. The black stone can move to cell 4 or 6. Note that a stone may move away from the opposing stone.

Examples2

Example 1
Input
```
2
3 3
Whiteking
```
Expected output
```
Blackking
```
Example 2
Input
```
2
3 5
Whiteking
```
Expected output
```
Whiteking
```