题目描述

现在你会和朋友玩这样一个游戏：你的朋友写下一个由 0 和 1 组成的序列。你选择一个连续的子序列（例如从第 3 位到第 5 位，包含端点），然后问他这个子序列中 1 的个数是偶数还是奇数。你的朋友会回答你的问题，之后你可以继续提问其他子序列。进而猜出完整的 0-1 序列。

你怀疑朋友的某些回答可能不正确，所以你想要证明他在说谎。为此，你需要编写一个程序来辅助你。程序会接收你提出的一系列问题，以及朋友给出的回答。程序的目标是找到​第一个必然错误的回答​—— 也就是说，存在一个 0-1 序列满足前 X 个回答，但不存在任何序列能满足前 X+1 个回答。

输入格式

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

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

第 $3$ 行开始是问题和答案，每行先有两个整数，表示你询问的段的开始位置和结束位置。然后是朋友的回答。odd表示有奇数个 $1$，even 表示有偶数个 $1$。

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

3

说明/提示

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