#include <iostream>
#include <string>
using namespace std;

string s;
bool decided[501][501];
bool dp[501][501];

//s[l, r)???cat??????true?????????
bool isCat( int l, int r ){
	if( decided[l][r] ){
		return dp[l][r];
	}
	if( l == r ){
		dp[l][r] = true;
		decided[l][r] = true;
		return true;
	}
	if( s[l] != 'm' ){
		dp[l][r] = false;
		decided[l][r] = true;
		return false;
	}
	if( s[r-1] != 'w' ){
		dp[l][r] = false;
		decided[l][r] = true;
		return false;
	}
	for( int i = l + 1; i < r - 1; i++ ){
		if( s[i] == 'e' ){
			if( isCat(l + 1, i) && isCat(i + 1, r - 1) ){
				dp[l][r] = true;
				decided[l][r] = true;
				return true;
			}
		}
	}
	dp[l][r] = false;
	decided[l][r] = true;
	return false;
}

int main()
{
	cin >> s;
	if( isCat(0, s.length()) ){
		cout << "Cat" << endl;
	}
	else{
		cout << "Rabbit" << endl;
	}
	return 0;
}
### Prompt

Construct a Cpp code solution to the problem outlined:

Example

Input

mmemewwemeww


Output

Cat

### Response

```cpp
#include <iostream>
#include <string>
using namespace std;

string s;
bool decided[501][501];
bool dp[501][501];

//s[l, r)???cat??????true?????????
bool isCat( int l, int r ){
	if( decided[l][r] ){
		return dp[l][r];
	}
	if( l == r ){
		dp[l][r] = true;
		decided[l][r] = true;
		return true;
	}
	if( s[l] != 'm' ){
		dp[l][r] = false;
		decided[l][r] = true;
		return false;
	}
	if( s[r-1] != 'w' ){
		dp[l][r] = false;
		decided[l][r] = true;
		return false;
	}
	for( int i = l + 1; i < r - 1; i++ ){
		if( s[i] == 'e' ){
			if( isCat(l + 1, i) && isCat(i + 1, r - 1) ){
				dp[l][r] = true;
				decided[l][r] = true;
				return true;
			}
		}
	}
	dp[l][r] = false;
	decided[l][r] = true;
	return false;
}

int main()
{
	cin >> s;
	if( isCat(0, s.length()) ){
		cout << "Cat" << endl;
	}
	else{
		cout << "Rabbit" << endl;
	}
	return 0;
}
```