题目描述

在一个 $n\times n$ 的点阵上，Alice 和 Bob 轮流在相邻的两个点之间画线。行号、列号均从 $1$ 开始，行号从上往下递增，列号从左往右递增。

一旦所有已画出的线中出现封闭的圈，游戏就结束。圈的面积不一定为 $1$。给定按时间顺序记录的 $m$ 次画线操作，请找出第一次出现圈是在第几步。

输入格式

第一行两个整数 $n,m$。接下来 $m$ 行，每行两个整数 $x,y$ 和一个字符。D 表示从 $(x,y)$ 连到 $(x+1,y)$；R 表示连到 $(x,y+1)$。保证端点在点阵内，且没有重复边。

输出格式

如果出现圈，输出第一次出现圈的步数；否则输出 draw。

样例

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

4

数据范围

$1\le n\le200$，$0\le m\le2n(n-1)$。