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

---

【题目描述】

　　有一个01序列，长度≤1000000000，现在有 \(n\) 条信息,每条信息的形式是"a b even/odd"， 表示序列的第 \(a\) 位到第 \(b\) 位元素之间的元素总和是偶数/奇数。

　　你的任务是对于这些给定的信息，输出第一个不正确的信息所在位置-1。信息的数目不超过 5000。 如果信息全部正确，即可以找到一个满足要求的01序列，那么输出 \(n\)。

【输入格式】

　　第一行一个整数 \(m\) 表示 01 序列的长度
　　第二行一个整数 \(n\) 表示信息的数目。
　　接下来是 \(n\) 条信息。

【输出格式】

　　输出第一条错误信息的位置-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

【数据限制】

　　\(100\%\) 的数据满足：01序列,长度 ≤1000000000。

【来源】

　　Mr.he