チエノとカカオは同じ喫茶店で働く姉妹である。2人はとても仲が良く、ある日、とあるテーブルゲームで遊ぶことになった。
ゲームはRマス×Cマスの盤面と、駒としてうさぎのTPを用いる。盤面の各マスは白か黒の色が塗られている。最初にTPを盤面の右下(R,C)におき、2人で次の行動を交互に行う。TPの現在の位置を(a,b)とすると、そこからジャンプ可能な位置(i,j)を1つ選び、TPをそこにジャンプさせる。TPがジャンプ可能な位置(i,j)は以下をすべて満たす。
自分のターンにTPをジャンプさせることができなくなった場合、負けとなる。
チエノが先手、カカオが後手でこのゲームを行う。カカオは頭の中でゲームを最後まで先読みすることができ、常に最適な行動をとる。この時、チエノが勝つ方法が存在するかどうかを判定せよ。
入力は以下の形式で与えられる。
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)の色を表し、”.”が白、"#”が黒を表す。
チエノが勝つ方法が存在する場合は”Chieno”を、存在しない場合は”Cacao”を1行に出力せよ。
3 3 2 ... ... ...
Chieno
3 3 2 #.# .#. #..
Cacao