1394: 奇偶

A和B在玩一个游戏：他写一个由0和1组成的序列。

A选其中的一段（比如第3位到第5位），问他这段里面有奇数个1还是偶数个1。

B回答你的问题，然后A继续问。

B有可能在撒谎。A要检查B的答案，指出在B的第几个回答一定有问题。

有问题的意思就是存在一个01序列满足这个回答前的所有回答，而且不存在序列

满足这个回答前的所有回答及这个回答。

第1行一个整数，是这个01序列的长度（<=1000000000)

第2行一个整数，是问题和答案的个数。

第3行开始是问题和答案，

每行先有两个整数，表示你询问的段的开始位置和结束位置。

然后是B的回答。odd表示有奇数个1，even表示有偶数个1。

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

3