Hopping Mind

Problem

Chieno and Cacao are sisters who work in the same coffee shop. The two are very close, and one day they decided to play a table game.

The game uses the board of R square x C square and the rabbit TP as a piece. Each square on the board is painted white or black. First, place the TP in the lower right corner (R, C) of the board, and the two perform the following actions alternately. Assuming that the current position of TP is (a, b), one jumpable position (i, j) is selected from there, and TP is made to jump there. The positions (i, j) where TP can jump satisfy all of the following.

1. 1 ≤ i ≤ R and 1 ≤ j ≤ C and i ≤ a and j ≤ b and 1 ≤ (a-i) + (b-j) ≤ K
2. (i, j) is a white square

If you can no longer jump TP on your turn, you lose.

Chieno is on the play and Cacao is on the play. Cacao can look ahead to the end of the game in his head and always behaves optimally. At this time, determine if there is a way for Chieno to win.

Constraints

• 1 ≤ R, C ≤ 1000
• 1 ≤ K ≤ 2000
• GR and C are “.”

Input

The input is given in the following format.

R C K G1,1 G1,2 ... G1,C G2,1 G2,2 ... G2, C :: GR, 1 GR, 2 ... GR, C

The first line is given three integers R, C, K separated by blanks. C "." Or "#" are given as board information in the next R line. Gi, j represents the color of the board position (i, j), "." Represents white, and "#" represents black.

Output

Print "Chieno" if there is a way for Chieno to win, or "Cacao" if it doesn't.

Examples

Input

3 3 2 ... ... ...

Output

Chieno

Input

3 3 2 .# .#. ..

Output

Cacao

inputFormat

Input

The input is given in the following format.

R C K G1,1 G1,2 ... G1,C G2,1 G2,2 ... G2, C :: GR, 1 GR, 2 ... GR, C

The first line is given three integers R, C, K separated by blanks. C "." Or "#" are given as board information in the next R line. Gi, j represents the color of the board position (i, j), "." Represents white, and "#" represents black.

outputFormat

Output

Print "Chieno" if there is a way for Chieno to win, or "Cacao" if it doesn't.

Examples

Input

3 3 2 ... ... ...

Output

Chieno

Input

3 3 2 .# .#. ..

Output

Cacao

样例

3 3 2
...
...
...

Chieno