1096. 小胖的奇偶

时间限制 1000 ms
内存限制 128 MB

题目描述

huyichen和xuzhenyi在玩一个游戏:他写一个由0和1组成的序列。
huyichen选其中的一段(比如第3位到第5位),问他这段里面有奇数个1
还是偶数个1。xuzhenyi回答你的问题,然后huyichen继续问。
xuzhenyi有可能在撒谎。huyichen要检查xuzhenyi的答案,指出在xuzhenyi的第几个回答一定有问题。
有问题的意思就是存在一个01序列满足这个回答前的所有回答,而且不存在序列
满足这个回答前的所有回答及这个回答。

输入数据

第 $1$ 行一个整数,是这个 $01$ 序列的长度 $(< 10^{8})$
第 $2$ 行一个整数,是问题和答案的个数。
第 $3$ 行开始是问题和答案,
每行先有两个整数,表示你询问的段的开始位置和结束位置。
然后是xuzhenyi的回答。odd表示有奇数个 $1, even$ 表示有偶数个 $1$ 。

输出数据

输出一行,一个数 $X,$ 表示存在一个 $01$ 序列满足第 $1$ 到第 $X$ 个回答,
但是不存在序列满足第 $1$ 到第 $X+1$ 个回答。如果所有回答都没问题,你就输出
所有回答的个数。

样例输入

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

样例输出

3

题目信息

未提交
未通过无法查看
未通过无法查看