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>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

struct BIT{
    // [1,n]
    int n; vector<ll> bit;
    // 初期化
    BIT(){}
    BIT(int _n){
        n = _n;
        bit = vector<ll>(n+1,0);
    }
    // sum of [1,i]
    ll sum(int i){
        ll s = 0;
        while(i>0){
            s += bit[i];
            i -= i & -i;
        }
        return s;
    }
    // add x in i-th element
    void add(int i, ll x){
        while(i<=n){
            bit[i] += x;
            i += i & -i;
        }
    }
    // [l,r]
    ll sum(int l, int r){
        return sum(r)-sum(l-1);
    }
};

const int M = 2020;
const int N = 3333;

BIT row[N],col[N];

int main(){
    int h,w,k;
    cin >>h >>w >>k;

    vector<string> s(h);
    rep(i,h) cin >>s[i];

    vector<vector<pair<int,int>>> v(h+w-1);
    rep(i,h)rep(j,w) v[i+j].pb({i, j});

    rep(i,N){
        row[i] = BIT(N);
        col[i] = BIT(N);
    }

    auto calc = [&](int y, int x, ll val){
        y -= M;
        x -= M;
        if(s[y][x] == '#') return 0;
        return (int)!val;
    };

    ll sum = 0;
    int pi = M, pj = M;
    vector<vector<int>> dp(N,vector<int>(N));
    rep(i,h+w-1){
        sort(all(v[i]));
        int V = v[i].size();

        int si = v[i][0].fi+M, sj = v[i][0].se+M;
        if(i>0){
            int ti = pi-k, tj = pj;
            while(ti<=pi){
                sum -= dp[ti][tj];
                ++ti;
                --tj;
            }
            sum += dp[pi][pj];

            if(pi == si) sum += col[sj].sum(si-k,si-1);
            else sum += row[si].sum(sj-k,sj-1);
        }

        dp[si][sj] = calc(si, sj, sum);
        ll tsum = sum;
        for(int j=1; j<V; ++j){
            int ti = v[i][j].fi+M, tj = v[i][j].se+M;
            tsum -= col[tj+1].sum(ti-k-1, ti-1-1);
            tsum += row[ti].sum(tj-k, tj-1);
            dp[ti][tj] = calc(ti, tj, tsum);
        }

        rep(j,V){
            int ti = v[i][j].fi+M, tj = v[i][j].se+M;
            row[ti].add(tj, dp[ti][tj]);
            col[tj].add(ti, dp[ti][tj]);
        }

        pi = si;
        pj = sj;
    }

    cout << (dp[M+h-1][M+w-1]?"Cacao":"Chieno") << endl;
    return 0;
}