#include <iostream>
#include <cstring>
#include <string>

using namespace std;

const int SIZE = 501;
char memo[SIZE][SIZE];

bool rec ( string& str, int begin ,int end )
{
	if ( begin > end ) {
		return true;
	}
	if ( begin == end ) {
		return false;
	}
	if ( str[begin] != 'm' || str[end] != 'w' ) {
		return false;
	}
	if ( memo[begin][end] != -1 ) {
		return ( bool )memo[begin][end];
	}
	bool result = false;
	for ( int i = begin + 1; i < end; ++i ) {
		if ( str[i] == 'e' ) {
			result |= rec( str, begin + 1, i - 1 ) && rec( str, i + 1, end - 1 );
		}
	}
	memo[begin][end] = ( char )result;
	return result;
}

int main()
{
	string str;
	while ( cin >> str  ) {
		memset( memo, -1, SIZE * SIZE );
		cout << ( rec( str, 0, str.size() - 1 ) ? "Cat" : "Rabbit" ) << endl;
	}
	return 0;
}
### Prompt

Construct a Cpp code solution to the problem outlined:

Example

Input

mmemewwemeww


Output

Cat

### Response

```cpp
#include <iostream>
#include <cstring>
#include <string>

using namespace std;

const int SIZE = 501;
char memo[SIZE][SIZE];

bool rec ( string& str, int begin ,int end )
{
	if ( begin > end ) {
		return true;
	}
	if ( begin == end ) {
		return false;
	}
	if ( str[begin] != 'm' || str[end] != 'w' ) {
		return false;
	}
	if ( memo[begin][end] != -1 ) {
		return ( bool )memo[begin][end];
	}
	bool result = false;
	for ( int i = begin + 1; i < end; ++i ) {
		if ( str[i] == 'e' ) {
			result |= rec( str, begin + 1, i - 1 ) && rec( str, i + 1, end - 1 );
		}
	}
	memo[begin][end] = ( char )result;
	return result;
}

int main()
{
	string str;
	while ( cin >> str  ) {
		memset( memo, -1, SIZE * SIZE );
		cout << ( rec( str, 0, str.size() - 1 ) ? "Cat" : "Rabbit" ) << endl;
	}
	return 0;
}
```