#include <bits/stdc++.h>

using namespace std;

vector<vector<int> > dp;
string s;

bool dfs(int l,int r) {
  if(dp[l][r]!=-1) return dp[l][r];
  if(l==r) return dp[l][r]=true;
  if(s[l]!='m'||s[r-1]!='w') return dp[l][r]=false;
  for(int i=l+1;i<r-1;++i)
    if(s[i]=='e')
      if(dfs(l+1,i)&&dfs(i+1,r-1)) return dp[l][r]=true;
  return dp[l][r]=false;
}

int main(){
  cin >> s;
  dp.assign(s.size(),vector<int>(s.size()+1,-1));
  if(dfs(0,s.size())) cout << "Cat" << endl;
  else cout << "Rabbit" << endl;
  
  return 0;
}

### Prompt

Create a solution in Cpp for the following problem:

Example

Input

mmemewwemeww


Output

Cat

### Response

```cpp
#include <bits/stdc++.h>

using namespace std;

vector<vector<int> > dp;
string s;

bool dfs(int l,int r) {
  if(dp[l][r]!=-1) return dp[l][r];
  if(l==r) return dp[l][r]=true;
  if(s[l]!='m'||s[r-1]!='w') return dp[l][r]=false;
  for(int i=l+1;i<r-1;++i)
    if(s[i]=='e')
      if(dfs(l+1,i)&&dfs(i+1,r-1)) return dp[l][r]=true;
  return dp[l][r]=false;
}

int main(){
  cin >> s;
  dp.assign(s.size(),vector<int>(s.size()+1,-1));
  if(dfs(0,s.size())) cout << "Cat" << endl;
  else cout << "Rabbit" << endl;
  
  return 0;
}

```