题目描述

你和你的朋友玩一个游戏。你的朋友写下一个由 0 和 1 组成的序列。你选择一个连续的子序列，然后问他这个子序列包含偶数个还是奇数个 1，你的朋友回答你的问题。然后重复这个步骤。你的任务是猜测整个数字序列。

你怀疑你的朋友的一些答案可能不正确，你想揭穿他的谎言。因此，你决定编写一个程序来帮助你解决这个问题。程序将接收你的一系列问题以及你从朋友那里得到的答案，目的是找到第一个错误的答案。

输入格式

输入的第一行包含一个数字 $n$ ，这是 01 序列的长度。这个长度小于或等于 $10^9$ 。

第二行有一个正整数 $m(1 \le m \le 5000)$ ，是提出的问题和答案的数量。

接下来 $m$ 行指定了问题和答案。每一行包含一个问题及其答案：两个整数（所选子序列中第一个和最后一个数字的位置）和一个单词，要么是“even”（偶数），要么是“odd”（奇数）（答案，即所选子序列中 1 的个数的奇偶性，其中“even”表示偶数个 1，“odd”表示奇数个 1）。

输出只有一行，包含一个整数X。数字X表示存在一个 0 和 1 的序列，满足前X个奇偶性条件，但没有序列满足X+1个条件。如果存在一个 0 和 1 的序列满足所有给定条件，那么X应该是提出的问题的总数。

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