CatChecker

Interview

Time limit8sMemory limit512 MB

Summary

Decide whether a string of m, e, w matches the grammar CAT := "" | 'm' CAT 'e' CAT 'w'.

Level: Medium5 of 10
Topics: String, Dynamic programming, Recursion, Implementation
Solved: No attempts yet

Problem

There is an animal whose appearance does not reveal whether it is a cat. You decide to judge it as a cat if its cry is a cat's cry, and as a rabbit otherwise.

A cat's cry is defined as follows.

"" (the empty string) is a cat's cry.
If $X$ and $Y$ are cat's cries, then 'm' + $X$ + 'e' + $Y$ + 'w' is a cat's cry. Here + denotes string concatenation.
Only the strings defined above are cat's cries.

In BNF, a cat's cry $CAT$ is defined as

$CAT$ := "" (the empty string) $|$ 'm' + $CAT$ + 'e' + $CAT$ + 'w'

A string $S$ representing a cry is given. Determine what the animal is from its cry.

Input

The input is given in the following format:

$S$

Output

If $S$ is a cat's cry, output "Cat"; otherwise, output "Rabbit", on one line.

Constraints

$S$ contains between 1 and 500 characters, inclusive. Each character in $S$ is 'm', 'e', or 'w'.

Examples2

Example 1
Input
```
mmemewwemeww
```
Expected output
```
Cat
```
Example 2
Input
```
mewmew
```
Expected output
```
Rabbit
```