#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<utility>
#include<queue>
#include<string>
using namespace std;
typedef pair<int, int> P;
#define _CRT_SECURE_NO_WARNINGS
int N;
char s[502];
int dp[502][502];
bool Serch(int l,int r) {
	if (l>r) {
		return true;
	}
	if (s[l] != 'm') {
		return false;
	}
	if (s[r] !='w') {
		return false;
	}
	if (dp[l][r]!=-1) {
		if (dp[l][r]==0) {
			return false;
		}
		else {
			return true;
		}
	}
	bool ans = false;

	for (int i = l + 1; i < r;i++) {
		if (s[i]=='e') {
			if (Serch(l + 1, i - 1) && Serch(i+1,r-1) ) {
				dp[l][r] = 1;
				ans = true;
				break;
			}
		}
	}
	if (ans==false) {
		dp[l][r] = false;
	}

	return ans;
	
}

int main() {
	bool ans;
	int end;
	
		scanf("%s", s);
	for (int i = 0; i < 500; i++) {
		if (s[i]!='m' && s[i] != 'e'&& s[i] != 'w') {
			end = i;
			for (int k = 0; k < i;k++) {
				for (int j = 0; j < i;j++) {
					dp[j][k] = -1;
				}
			}
			break;
		}
	}
	ans = Serch(0,end-1);

	if (ans) {
		printf("Cat\n");
	}
	else {
		printf("Rabbit\n");
	}
	return 0;
}
### Prompt

Your challenge is to write a CPP solution to the following problem:

Example

Input

mmemewwemeww


Output

Cat

### Response

```cpp
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<utility>
#include<queue>
#include<string>
using namespace std;
typedef pair<int, int> P;
#define _CRT_SECURE_NO_WARNINGS
int N;
char s[502];
int dp[502][502];
bool Serch(int l,int r) {
	if (l>r) {
		return true;
	}
	if (s[l] != 'm') {
		return false;
	}
	if (s[r] !='w') {
		return false;
	}
	if (dp[l][r]!=-1) {
		if (dp[l][r]==0) {
			return false;
		}
		else {
			return true;
		}
	}
	bool ans = false;

	for (int i = l + 1; i < r;i++) {
		if (s[i]=='e') {
			if (Serch(l + 1, i - 1) && Serch(i+1,r-1) ) {
				dp[l][r] = 1;
				ans = true;
				break;
			}
		}
	}
	if (ans==false) {
		dp[l][r] = false;
	}

	return ans;
	
}

int main() {
	bool ans;
	int end;
	
		scanf("%s", s);
	for (int i = 0; i < 500; i++) {
		if (s[i]!='m' && s[i] != 'e'&& s[i] != 'w') {
			end = i;
			for (int k = 0; k < i;k++) {
				for (int j = 0; j < i;j++) {
					dp[j][k] = -1;
				}
			}
			break;
		}
	}
	ans = Serch(0,end-1);

	if (ans) {
		printf("Cat\n");
	}
	else {
		printf("Rabbit\n");
	}
	return 0;
}
```