Problem: 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

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define SIZE 1005

int H,W,K;
int table[SIZE][SIZE];
char base_map[SIZE][SIZE];


int main(){

	scanf("%d %d %d",&H,&W,&K);

	for(int row = 0; row < H; row++){

		scanf("%s",base_map[row]);
	}

	table[0][0] = -1;
	int North,West;

	for(int row = 0; row < H; row++){
		for(int col = 0; col < W; col++){
			if(row == 0 && col == 0)continue;

			North = -1,West = -1;

			if(row > 0){
				if(base_map[row-1][col] == '.' && table[row-1][col] <= 0){

					North = K;
				}else{

					North = table[row-1][col]-1;
				}
			}
			if(col > 0){
				if(base_map[row][col-1] == '.' && table[row][col-1] <= 0){

					West = K;

				}else{

					West = table[row][col-1]-1;
				}

			}
			table[row][col] = max(North,West);
		}
	}

	if(table[H-1][W-1] > 0){

		printf("Chieno\n");

	}else{

		printf("Cacao\n");
	}

	return 0;
}