题目描述

有一个01序列,长度<=1000000000。

现在有n条信息,每条信息的形式是－a b even/odd。表示第a位到第b位元素之间的元素总和是偶数/奇数。

你的任务是对于这些给定的信息，输出第一个不正确的信息所在位置。信息的数目不超过10000。

如果信息全部正确，即可以找到一个满足要求的01序列，那么输出n。

输入格式

第一行一个整数m表示01序列的长度；

第二行一个整数n表示信息的数目。

接下来是n条信息

输出格式

一个按要求的整数

input

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

output

3

{因为第4个信息是不正确的，所以输出3，表示从1到3条信息都是正确的}

数据规模与约定

poj1733 ceoi1999 时间限制：1s 空间限制：256MB