#include <bits/stdc++.h>
 
using namespace std;

map<string, bool> memo;

bool parse(string s) {
  if(memo.find(s) != memo.end()) return memo[s];
  //cout << s << endl;
  if(s == "") return true;
  if(s == "mew") return true;
  int const size = s.size();
  
  bool ok = 0;
  for(int i=1; i<size; i++) {
    if(s[i] == 'e') {
      string temp;
      string t = "m";
      if(i-1>=0) {
	if(parse(temp = s.substr(1, i-1))) t+=temp;
	else continue;
      }
      t += "e";
      if(size-i-2>=0) {
	if(parse(temp = s.substr(i+1, size-i-2))) t+=temp;
	else continue;
      }
      t +="w";
      ok |= s == t;
      //cout << (ok ? "true: " : "false: ") << s  << " " << t<< endl;
    }
  }
  return memo[s] = ok;
}

string checker(string s) {
  return parse(s) ? "Cat" : "Rabbit"; 
}

int main() {
  string s; cin >> s;
  
  cout << checker(s) << 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;

map<string, bool> memo;

bool parse(string s) {
  if(memo.find(s) != memo.end()) return memo[s];
  //cout << s << endl;
  if(s == "") return true;
  if(s == "mew") return true;
  int const size = s.size();
  
  bool ok = 0;
  for(int i=1; i<size; i++) {
    if(s[i] == 'e') {
      string temp;
      string t = "m";
      if(i-1>=0) {
	if(parse(temp = s.substr(1, i-1))) t+=temp;
	else continue;
      }
      t += "e";
      if(size-i-2>=0) {
	if(parse(temp = s.substr(i+1, size-i-2))) t+=temp;
	else continue;
      }
      t +="w";
      ok |= s == t;
      //cout << (ok ? "true: " : "false: ") << s  << " " << t<< endl;
    }
  }
  return memo[s] = ok;
}

string checker(string s) {
  return parse(s) ? "Cat" : "Rabbit"; 
}

int main() {
  string s; cin >> s;
  
  cout << checker(s) << endl;
  
  return 0;
}
```