你时不时会和你的朋友玩下面这个游戏。你的朋友写下一个由$0$和$1$组成的序列。你选择一个连续的子序列（例如从第$3$位到第$5$位（包括第$3$位和第$5$位）的子序列），然后问他这个子序列中$1$的个数是偶数还是奇数。你的朋友回答你的问题，然后你可以再问他另一个子序列的情况，如此等等。你的任务是猜出整个数字序列。

你怀疑你朋友的一些回答可能不正确，并且你想证明他在说谎。因此你决定编写一个程序来帮助你处理这件事。这个程序将接收一系列你提出的问题以及你从朋友那里得到的答案。这个程序的目的是找到第一个被证明是错误的答案，也就是说，存在一个序列满足之前所有问题的答案，但不存在任何一个序列能满足这个答案。

输入

输入的第一行包含一个数字，它是由$0$和$1$组成的序列的长度。这个长度小于或等于$1000000000$。在第二行，有一个正整数，它是所问问题的数量以及对应的答案数量。问题和答案的数量小于或等于$5000$。剩下的行指定了问题和答案。每一行包含一个问题及其答案：两个整数（所选子序列的第一个和最后一个数字的位置）以及一个单词，这个单词要么是“$even$”（偶数）要么是“$odd$”（奇数）（答案，即所选子序列中$1$的个数的奇偶性，其中“$even$”表示$1$的个数为偶数，“$odd$”表示$1$的个数为奇数）。

输出

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

输入数据1

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

输出数据1

3

来源

CEOI 1999