时间限制：1秒　　内存限制：256M

---

【问题描述】

　　你和你的朋友玩一个游戏。你的朋友写下来一连串的 0 或者 1。你选择一个连续的子序列然后问他，这个子序列包含 1 的个数是奇数还是偶数。你的朋友回答完你的问题，接着你问下一个问题。

　　你怀疑你朋友的一些答案可能是错误的，你决定写一个程序来帮忙。程序将接受一系列你的问题及你朋友的回答，程序的目的是找到第一个错误的回答 \(i\)，也就是存在一个序列满足前 \(i-1\) 个问题的答案，但是不满足前 \(i\) 个问题。

【输入格式】

　　第一行有一个整数 \(L\)，是这个 01 序列的长度。第二行是一个整数 \(N\)，是问题及其答案的数目,接下来 \(N\) 行描述问题和答案。每一行包含一个问题和这个问题的答案：两个整数（子序列的起始位置和结束位置）和一个单词 "even" 或 者 "odd"、"even"表示这个子序列中的 '1' 的个数是偶数，'odd' 则表示是奇数。

【输出格式】

　　输出一行一个整数 \(X\)。表示存在一个 01 序列满足前面的 \(X\) 个问题，但是不存在一个 01 序列满足前 \(X+1\) 个问题，如果存在一个序列满足所有问题，则输出 \(N\)。

【输入输出样例1】

　Input

10
5
1 2 even
3 4 odd
5 6 even
1 6 even
7 10 odd

　Output

3

【输入输出样例2】

　Input

10
 5
1 2 even
1 4 even
2 4 odd
1 10 even
3 10 even

　Output

5

【数据限制】

　　序列长度 L<=1000000000，询问及回答数 N<=5000

【来源】

　　Mr.he