#include <iostream>
#include <map>

using namespace std;

map<string,bool> m;

bool check(string s){
  if (m[s]) {
    return false;
  }

  if (s == "") {
    return true;
  }

  int len = (int)s.size();
  if (s[0] != 'm' || s[len-1] != 'w') {
    m[s] = true;
    return false;
  }

  if (len < 3) {
    m[s] = true;
    return false;
  } 

  len = (int)s.size();
  s.erase(--s.end());
  s.erase(s.begin());

  for (int i = 0 ; i < len ; i++) {
    if (s[i] == 'e') {
      string X = s.substr(0,i);
      string Y = s.substr(i+1,len);
 
      int ok = 2;
      if (check(X)) {
	ok--;
      } else {
	m[X] = true;
      }

      if (check(Y)) {
	ok--;
      } else {
	m[Y] = true;
      }

      if (!ok) {
	return true;
      }

    } 
  }

  m[s] = true;
  return false;
}

int main(){
  string s;

  cin >> s;
  if (check(s)) {
    cout << "Cat" << endl;
  } else {
    cout << "Rabbit" << endl;
  }

  return 0;
}
### Prompt

Please create a solution in Cpp to the following problem:

Example

Input

mmemewwemeww


Output

Cat

### Response

```cpp
#include <iostream>
#include <map>

using namespace std;

map<string,bool> m;

bool check(string s){
  if (m[s]) {
    return false;
  }

  if (s == "") {
    return true;
  }

  int len = (int)s.size();
  if (s[0] != 'm' || s[len-1] != 'w') {
    m[s] = true;
    return false;
  }

  if (len < 3) {
    m[s] = true;
    return false;
  } 

  len = (int)s.size();
  s.erase(--s.end());
  s.erase(s.begin());

  for (int i = 0 ; i < len ; i++) {
    if (s[i] == 'e') {
      string X = s.substr(0,i);
      string Y = s.substr(i+1,len);
 
      int ok = 2;
      if (check(X)) {
	ok--;
      } else {
	m[X] = true;
      }

      if (check(Y)) {
	ok--;
      } else {
	m[Y] = true;
      }

      if (!ok) {
	return true;
      }

    } 
  }

  m[s] = true;
  return false;
}

int main(){
  string s;

  cin >> s;
  if (check(s)) {
    cout << "Cat" << endl;
  } else {
    cout << "Rabbit" << endl;
  }

  return 0;
}
```