#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;
set<string> cat, rabbit;

bool isCat(string S) {
    //cerr << S << endl;
    if(cat.find(S) != cat.end()) return true;
    if(rabbit.find(S) != rabbit.end()) return false;
    if(S == "") return true;
    if(S[0] != 'm' || S.back() != 'w') {
        rabbit.insert(S);
        return false;
    }
    int n = S.size();
    for(int i = 1; i + 1 < S.size(); i++) {
        if(S[i] != 'e') continue;
        if(!isCat(S.substr(1, i - 1))) continue;
        if(!isCat(S.substr(i + 1, n - i - 2))) continue;
        cat.insert(S);
        return true;
    }
    rabbit.insert(S);
    return false;
}

int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S;
    cin >> S;
    if(isCat(S)) cout << "Cat" << endl;
    else cout << "Rabbit" << endl;
    return 0;
}


### Prompt

Generate a Cpp solution to the following problem:

Example

Input

mmemewwemeww


Output

Cat

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;
set<string> cat, rabbit;

bool isCat(string S) {
    //cerr << S << endl;
    if(cat.find(S) != cat.end()) return true;
    if(rabbit.find(S) != rabbit.end()) return false;
    if(S == "") return true;
    if(S[0] != 'm' || S.back() != 'w') {
        rabbit.insert(S);
        return false;
    }
    int n = S.size();
    for(int i = 1; i + 1 < S.size(); i++) {
        if(S[i] != 'e') continue;
        if(!isCat(S.substr(1, i - 1))) continue;
        if(!isCat(S.substr(i + 1, n - i - 2))) continue;
        cat.insert(S);
        return true;
    }
    rabbit.insert(S);
    return false;
}

int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S;
    cin >> S;
    if(isCat(S)) cout << "Cat" << endl;
    else cout << "Rabbit" << endl;
    return 0;
}


```