#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;

int N;
string S;
map<pair<int, int>, int> mp;

bool is(int s, int t) {
	if (s == t) return true;
	if (t - s < 3 || S[s] != 'm' || S[t - 1] != 'w') return false;

	P p(s, t);
	int r = mp[p];
	if (r) return r == 1 ? true : false;

	for (int i = s + 1; i < t - 1; i++) {
		if (S[i] == 'e' && is(s + 1, i) && is(i + 1, t - 1)) {
			mp[p] = 1;
			return true;
		}
	}
	mp[p] = -1;
	return false;
}

int main()
{
	cin >> S;
	N = S.size();
	cout << (is(0, N) ? "Cat" : "Rabbit") << endl;
	return 0;
}
### Prompt

Generate a cpp solution to the following problem:

Example

Input

mmemewwemeww


Output

Cat

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;

int N;
string S;
map<pair<int, int>, int> mp;

bool is(int s, int t) {
	if (s == t) return true;
	if (t - s < 3 || S[s] != 'm' || S[t - 1] != 'w') return false;

	P p(s, t);
	int r = mp[p];
	if (r) return r == 1 ? true : false;

	for (int i = s + 1; i < t - 1; i++) {
		if (S[i] == 'e' && is(s + 1, i) && is(i + 1, t - 1)) {
			mp[p] = 1;
			return true;
		}
	}
	mp[p] = -1;
	return false;
}

int main()
{
	cin >> S;
	N = S.size();
	cout << (is(0, N) ? "Cat" : "Rabbit") << endl;
	return 0;
}
```