11664 - Langton's Ant

數學家 Christopher Langton 設計一套簡單的細胞自動機，名為 Langton's ant，根據給定的一個簡單行為規則但卻有趣的行為，這個行為是數學家研究的課題。


從分析螞蟻行為以及 Langton 的細胞自動機，根據給定的當下自動機的狀態，以及全自動的螞蟻能力，將會發現螞蟻呈現一個特別的走訪模式，進行探索這個世界。

螞蟻的世界為一個 n x n 的平面，每一格塗上藍色或者是紅色，而每一格座標定義 (i, j) (1 <= i, j <= n)，螞蟻的移動規則如下：

• 如果當前在藍色格子，她會將格子變成紅色，並且向左轉 90 度，並且朝這個方向前進一格。
• 如果當前在藍色格子，她會將格子變成紅色，並且向右轉 90 度，並且朝這個方向前進一格。
• 如果移動失敗，即掉出格子外，螞蟻則宣告死亡。

例如：假設有一隻螞蟻現在在紅色格子上，並且面朝東方，而牠會將這格變成紅色，並且面朝南方，如果南方沒有格子可走，那麼牠則會死亡 。反之，則會走下南方的那一格，並且重複步驟進行移動。


根據給定的狀態以及當前螞蟻所在位置，你的任務是要決定螞蟻能不能到達 (n, n)。

假設螞蟻一開始面朝北方。

Input 

由於狀態是 n x n ，可以表示 n² bits 的二進制數字，方便起見定義 0 是藍色，1 是紅色。而給定的順序為由左而右、由下而上。

例如：0100 (十進制為 4) 表示一個 2 x 2 的狀態

blue	blue
blue	red

而  011010100 (十進制為 212) 表示一個 3 x 3 的狀態

red	blue	blue
blue	red	blue
blue	red	red

額外補充：相對應座標如下 (x, y)

(3,1)	(3,2)	(3,3)
(2,1)	(2,2)	(2,3)
(1,1)	(1,2)	(1,3)

輸入有多組測資，每組測資第一行會有四個整數 n, c, x, y

• n ( 1 <=  n  <= 16)：狀態的大小
• c ( 0 <= c  < 2⁽ⁿ²⁾)：一個十進制表示  n²-bit 二進制數，其數值為上描述。
• (x, y)：表示螞蟻一開始所在的位置 (1 <= x, y <= n)。

當 n = c = x = y = 0 結束程式。

Output 

對於每組測資，輸出格式為以下兩種的其中一種：

• `Yes'：如果螞蟻能夠抵達 (n, n)
• `Kaputt!'：如果螞蟻無法抵達 (n, n)

對於每組測資，保證一定會在有限步數內得到其中一種結果。

Sample Input 

2 8 1 1
2 4 1 1
2 15 1 1
0 0 0 0

Sample Output 

Yes
Kaputt!
Kaputt!

---