Imagination Castle
Contest: COMPFEST 15 - Preliminary Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 2300
Tags: dp, games, two pointers

Given a chessboard of size $$$N \times M$$$ ($$$N$$$ rows and $$$M$$$ columns). Each row is numbered from $$$1$$$ to $$$N$$$ from top to bottom and each column is numbered from $$$1$$$ to $$$M$$$ from left to right. The tile in row $$$r$$$ and column $$$c$$$ is denoted as $$$(r,c)$$$. There exists $$$K$$$ distinct special tiles on the chessboard with the $$$i$$$-th special tile being tile $$$(X_i,Y_i)$$$. It is guaranteed that tile $$$(1,1)$$$ is not a special tile.

A new chess piece has been invented, which is the castle. The castle moves similarly to a rook in regular chess, but slightly differently. In one move, a castle that is on some tile can only move to another tile in the same row or in the same column, but only in the right direction or the down direction. Formally, in one move, the castle on tile $$$(r,c)$$$ can only move to tile $$$(r',c')$$$ if and only if one of the following two conditions is satisfied:

- $$$r'=r$$$ and $$$c'>c$$$.
- $$$c'=c$$$ and $$$r'>r$$$.

Chaneka and Bhinneka will play a game. In the beginning of the game, there is a castle in tile $$$(1,1)$$$. The two players will play alternatingly with Chaneka going first. In one turn, the player on that turn must move the castle following the movement rules of the castle.

If a player moves the castle to a special tile on her turn, then that player wins the game and the game ends. If on a turn, the castle cannot be moved, the player on that turn loses and the game ends.

Given the size of the board and the locations of each special tile. Determine the winner of this game if Chaneka and Bhinneka plays optimally.

Input format:
The first line contains three integers $$$N$$$, $$$M$$$, and $$$K$$$ ($$$1 \leq N,M \leq 2 \cdot 10^5$$$; $$$0 \leq K \leq \min(N \times M - 1, 2\cdot10^5)$$$) — the size of the chessboard and the number of special tiles.

The $$$i$$$-th of the next $$$K$$$ lines contains two integers $$$X_i$$$ and $$$Y_i$$$ ($$$1\leq X_i\leq N$$$; $$$1\leq Y_i\leq M$$$; $$$(X_i, Y_i) \neq (1,1)$$$) — the location of each special tile. The special tiles are pairwise distinct.

Output format:
Output Chaneka if Chaneka is the winner, output Bhinneka if Bhinneka is the winner.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first example, the following is an illustration of the chessboard in the beginning of the game.

Chaneka can move the castle to special tile $$$(1,3)$$$ or $$$(1,5)$$$ directly on her first turn. Therefore, Chaneka is the winner.

In the second example, the following is an illustration of the chessboard in the beginning of the game.

Chaneka can only move the castle to tile $$$(1, 2)$$$ or $$$(2, 1)$$$ on her first turn. Whatever Chaneka does, Bhinneka will be able to directly move the castle to tile $$$(2, 2)$$$. After that, on Chaneka's turn, she cannot move the castle, so Chaneka loses. Therefore, Bhinneka is the winner.

Example input:
4 5 3
1 3
4 4
1 5

Example output:
Chaneka

Example input:
2 2 0

Example output:
Bhinneka

Editorial:
Define a winning tile as a tile where if a player starts a turn with the castle in that tile, she will have a strategy to win. Define a losing tile as a tile where if a player starts a turn with the castle in that tile, no matter what she does, the other player will always have a strategy to win. We can see each special tile as a losing tile.
We can solve the problem by finding which tiles are the losing tiles. We can do that by doing "backtrack" from the bottom right corner of the board. Maintain a pointer $$$(r,c)$$$ which means that we have solved all tiles $$$(r',c')$$$ with $$$r'>r$$$ or $$$c'>c$$$. So initially, $$$(r,c)=(N,M)$$$ (no tiles are solved).
There are three cases for each iteration of the pointer:
• If there is at least one special tile $$$(r',c')$$$ satisfying $$$r'=r$$$ and $$$c'\geq c$$$, then all non-special tiles $$$(r' ',c' ')$$$ satisfying $$$r' '=r$$$ and $$$c' '<c$$$ are winning tiles. Then, move $$$(r,c)$$$ one step up.
• If there is at least one special tile $$$(r',c')$$$ satisfying $$$c'=c$$$ and $$$r'\geq r$$$, then all non-special tiles $$$(r' ',c' ')$$$ satisfying $$$c' '=c$$$ and $$$r' '<r$$$ are winning tiles. Then, move $$$(r,c)$$$ one step to the left.
• If neither of the cases above holds, then $$$(r,c)$$$ itself is a losing tile and all non-special tiles $$$(r' ',c' ')$$$ satisfying one of the following is a winning tile:   $$$r' '=r$$$ and $$$c' '<c$$$  $$$c' '=c$$$ and $$$r' '<r$$$  Then, move $$$(r,c)$$$ one step up and to the left.
• $$$r' '=r$$$ and $$$c' '<c$$$
• $$$c' '=c$$$ and $$$r' '<r$$$
Chaneka wins if $$$(1,1)$$$ is a winning tile. Bhinneka wins if $$$(1,1)$$$ is a losing tile.
Time complexity: $$$O(N+M+K)$$$