#include <cstdio>
#include <cassert>
#include <algorithm>
#include <string>
#include <vector>

std::vector<std::vector<int>> memo;

bool is_cat(const std::string &s, size_t il, size_t ir) {
  if (memo[il][ir] > -1) return memo[il][ir];

  // fprintf(stderr, "\"%s\"[%zu:%zu] (\"%s\")\n", s.c_str(), il, ir, s.substr(il, ir-il).c_str());
  int &res=memo[il][ir];
  if (il == ir) return (res = 1);
  if ((ir-il) % 3 > 0) return (res = 0);
  if (!(s[il] == 'm' && s[ir-1] == 'w')) return (res = 0);

  for (size_t i=il+1; i+1<ir; i+=3) {
    if (s[i] != 'e') continue;
    if (is_cat(s, il+1, i) && is_cat(s, i+1, ir-1)) return (res = 1);
  }
  return (res = 0);
}

int main() {
  char buf[512];
  scanf("%s", buf);
  std::string s=buf;

  if (s.length() % 3 > 0)
    return !printf("Rabbit\n");

  memo.assign(s.length()+1, std::vector<int>(s.length()+1, -1));
  printf("%s\n", is_cat(s, 0, s.length())? "Cat":"Rabbit");
}


### Prompt

Your task is to create a Cpp solution to the following problem:

Example

Input

mmemewwemeww


Output

Cat

### Response

```cpp
#include <cstdio>
#include <cassert>
#include <algorithm>
#include <string>
#include <vector>

std::vector<std::vector<int>> memo;

bool is_cat(const std::string &s, size_t il, size_t ir) {
  if (memo[il][ir] > -1) return memo[il][ir];

  // fprintf(stderr, "\"%s\"[%zu:%zu] (\"%s\")\n", s.c_str(), il, ir, s.substr(il, ir-il).c_str());
  int &res=memo[il][ir];
  if (il == ir) return (res = 1);
  if ((ir-il) % 3 > 0) return (res = 0);
  if (!(s[il] == 'm' && s[ir-1] == 'w')) return (res = 0);

  for (size_t i=il+1; i+1<ir; i+=3) {
    if (s[i] != 'e') continue;
    if (is_cat(s, il+1, i) && is_cat(s, i+1, ir-1)) return (res = 1);
  }
  return (res = 0);
}

int main() {
  char buf[512];
  scanf("%s", buf);
  std::string s=buf;

  if (s.length() % 3 > 0)
    return !printf("Rabbit\n");

  memo.assign(s.length()+1, std::vector<int>(s.length()+1, -1));
  printf("%s\n", is_cat(s, 0, s.length())? "Cat":"Rabbit");
}


```