Langton's Ant — Eolymp

Input

The configuration of an $n \times n$ n \times n world can be represented as a non-negative integer, using $n^{2}$ n^2 bits in binary notation. We use the following conventions: $0$ for blue, $1$ for red, and the binary representation identifies the cells from left to right, bottom to top (most significant bit to least significant bit). For example, $0100$ ( $4$ in decimal) represents a $2 \times 2$ 2 \times 2 world with the following configuration:

Similarly, $011010100$ ( $212$ in decimal) represents a $3 \times 3$ 3 \times 3 world with the configuration:

The input contains multiple test cases. Each case is a line with four integers: $n$ , $c$ , $x$ , $y$ , separated by spaces. They mean:

$n$ ( $1 \leq n \leq 16$ 1 \leq n \leq 16): The world size.
$c$ ( $0 \leq c < 2^{n^{2}}$ 0 \leq c < 2^{n^2}): Decimal representation of the $n^{2}$ n^2-bit configuration.
$(x, y)$ : Initial coordinates of the ant ( $1 \leq x, y \leq n$ 1 \leq x, y \leq n), where $(n, n)$ corresponds to the least significant bit of $c$ .

End of input: $n = c = x = y = 0$ n = c = x = y = 0.

Output

For each test case, output:

Yes if the ant reaches cell $(n, n)$ from the initial position.
Kaputt! if it dies before reaching cell $(n, n)$ .

It is guaranteed that for each test case, after a finite number of steps, the ant will either reach $(n, n)$ or die before reaching it.

Examples

Example 1

Loading