Hopping Mind

Time Limit : 1 sec, Memory Limit : 262144 KB

Problem I: Hopping Mind

Problem

チエノとカカオは同じ喫茶店で働く姉妹である。2人はとても仲が良く、ある日、とあるテーブルゲームで遊ぶことになった。

ゲームはRマス×Cマスの盤面と、駒としてうさぎのTPを用いる。盤面の各マスは白か黒の色が塗られている。最初にTPを盤面の右下(R,C)におき、2人で次の行動を交互に行う。TPの現在の位置を(a,b)とすると、そこからジャンプ可能な位置(i,j)を1つ選び、TPをそこにジャンプさせる。TPがジャンプ可能な位置(i,j)は以下をすべて満たす。

  1. 1 ≤ iR かつ 1 ≤ jC かつ ia かつ jb かつ 1 ≤ (a-i) + (b-j) ≤ K
  2. (i,j)は白いマスである

自分のターンにTPをジャンプさせることができなくなった場合、負けとなる。

チエノが先手、カカオが後手でこのゲームを行う。カカオは頭の中でゲームを最後まで先読みすることができ、常に最適な行動をとる。この時、チエノが勝つ方法が存在するかどうかを判定せよ。

Input

入力は以下の形式で与えられる。

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

1行目に3つの整数R,C,Kが空白区切りで与えられる。次のR行に盤面の情報としてC個の".”または"#”が与えられる。Gi,jは盤面の位置(i,j)の色を表し、”.”が白、"#”が黒を表す。

Constraints

  • 1 ≤ R,C ≤ 1000
  • 1 ≤ K ≤ 2000
  • GR,Cは“.”である

Output

チエノが勝つ方法が存在する場合は”Chieno”を、存在しない場合は”Cacao”を1行に出力せよ。

Sample Input1

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

Sample Output1

Chieno

Sample Input2

3 3 2
#.#
.#.
#..

Sample Output2

Cacao