#include<bits/stdc++.h>
using namespace std;
map<string,bool> used;

bool rec(string str){
  if(used.find(str) != used.end()) return used[str];

  if(str.empty()) return true;
  if(str[0] != 'm' || str[str.size() - 1] != 'w') return used[str] = false;

  //適当に真ん中を決める
  for(int i = 1; i < str.size() - 1; i++){
    if(str[i] == 'e'){
      if(i == 1 || i == str.size() - 2 || (i >= 4 || i <= str.size() - 5)){ //可能性がありそう(てきとー
        string right = str.substr( 1, i - 1);
        string left = str.substr( i + 1, str.size() - i - 2);
        if(rec(right) && rec(left)) return used[str] = true;
      } 
    }
  }
  return used[str] = false;
}

int main(){
  string str;
  cin >> str;

  if(rec(str)) puts("Cat");
  else puts("Rabbit");

}
### Prompt

Please create a solution in Cpp to the following problem:

Example

Input

mmemewwemeww


Output

Cat

### Response

```cpp
#include<bits/stdc++.h>
using namespace std;
map<string,bool> used;

bool rec(string str){
  if(used.find(str) != used.end()) return used[str];

  if(str.empty()) return true;
  if(str[0] != 'm' || str[str.size() - 1] != 'w') return used[str] = false;

  //適当に真ん中を決める
  for(int i = 1; i < str.size() - 1; i++){
    if(str[i] == 'e'){
      if(i == 1 || i == str.size() - 2 || (i >= 4 || i <= str.size() - 5)){ //可能性がありそう(てきとー
        string right = str.substr( 1, i - 1);
        string left = str.substr( i + 1, str.size() - i - 2);
        if(rec(right) && rec(left)) return used[str] = true;
      } 
    }
  }
  return used[str] = false;
}

int main(){
  string str;
  cin >> str;

  if(rec(str)) puts("Cat");
  else puts("Rabbit");

}
```