题目描述

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

输入格式

第 $1$ 行一个整数 $n$，是这个 $01$ 序列的长度。

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

第 $3$ 行开始是问题和答案，每行先有两个整数，表示你询问的段的开始位置和结束位置。然后是 Bob 的回答。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

10
1
9 9 odd

1

1010
2
749 906 even
325 1008 even

2

数据范围与约定

对于 $100\%$ 的数据，$1 \le n \leq 10^9$，$m \leq 5 \times 10^3$。