The Loop Game

Special for beginners, ^_^

Problem Description

Alice and Bob played an old game: first draw an $n \times n$ grid of points ($n = 3$ in the picture below).

Then the two of them take turns drawing red edges and blue edges between adjacent points:

until a closed loop is formed (its area need not be 1); the person who "closes the loop" wins. Because the board is so large ($n \le 200$), their games last very long! They do not even know during the game who has won. So write a program to help them determine whether the game has ended.

Input Format

The first line of input contains two integers $n$ and $m$. $m$ means that a total of $m$ edges are drawn. The next $m$ lines each first give two numbers $(x, y)$, the coordinates of the starting point of the edge, followed by a space and a character: if the character is D, an edge is drawn downward; if it is R, an edge is drawn to the right. The input contains no repeated edges, but edges may go out of bounds upward or downward.

Output Format

One line: the step at which the game ends. If it has not ended after $m$ steps, output the single word draw.

Sample Input 1

3 5
1 1 D
1 1 R
1 2 D
2 1 R
2 2 D

Sample Output 1

4

Constraints

1s, 1024KiB for each test case.