#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000000;
#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);++i)
#define rep(i,n) REP(i, 0, n)
typedef long long int i64;
typedef pair<int, int> pint;
string s;
bool dp[501][501];
bool used[501][501];
bool dfs(int l, int r) {
    if(l > r) return 0;
    if(used[l][r]) return dp[l][r];
    used[l][r] = true;
    if(l == r) return dp[l][r] = true;
    if(s[l] != 'm' || s[r - 1] != 'w') return false;
    REP(i, l + 1, r - 1) {
        if(s[i] == 'e') {
            bool a = dfs(l + 1, i);
            bool b = dfs(i + 1, r - 1);
            if(a && b) {
                dp[l][r] = true;
                break;
            }
        }
    }
    return dp[l][r];
}
int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    memset(dp, 0, sizeof(dp));
    memset(used, 0, sizeof(used));
    cin >> s;
    if(dfs(0, s.length())) cout << "Cat" << endl;
    else cout << "Rabbit" << endl;
    return 0;
}
### Prompt

Your challenge is to write a CPP solution to the following problem:

Example

Input

mmemewwemeww


Output

Cat

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000000;
#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);++i)
#define rep(i,n) REP(i, 0, n)
typedef long long int i64;
typedef pair<int, int> pint;
string s;
bool dp[501][501];
bool used[501][501];
bool dfs(int l, int r) {
    if(l > r) return 0;
    if(used[l][r]) return dp[l][r];
    used[l][r] = true;
    if(l == r) return dp[l][r] = true;
    if(s[l] != 'm' || s[r - 1] != 'w') return false;
    REP(i, l + 1, r - 1) {
        if(s[i] == 'e') {
            bool a = dfs(l + 1, i);
            bool b = dfs(i + 1, r - 1);
            if(a && b) {
                dp[l][r] = true;
                break;
            }
        }
    }
    return dp[l][r];
}
int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    memset(dp, 0, sizeof(dp));
    memset(used, 0, sizeof(used));
    cin >> s;
    if(dfs(0, s.length())) cout << "Cat" << endl;
    else cout << "Rabbit" << endl;
    return 0;
}
```