偶尔你跟朋友玩以下的游戏：你的朋友写下一串包含 1 和 0 的数串让你猜，你可以从中选择 一个连续的子串（例如其中的第 3 到第 5 个数字）问他，该子串中包含了奇数个还是偶数个 1，他会回答你的问题，然后你可以问其他子串，等等。

Problem

你的任务是猜出完整的子串。你怀疑你的朋友的答案可能有错，你想质疑他的错误。 所以 要写这个程序帮忙验证。程序接受一系列你的问题以及你朋友给出的答案。程序的目标是找 出错误的第一个答案，也就是某一子串满足先前的所有答案，而不满足当前这个答案。

Input

输入一系列的点。 首行为整个数串的长度 n(1<=n<=1000000000)，。第二行为一个正整数， 表示问题及答案数 number(0<=number<=5000)。之后每行表示问题及答案。格式：2 个整数 （即子串的第一个及最后一个数位），答案为一个单词：'even'（偶）,或'odd'（奇），即选择 的子串中 1 的个数是奇数个，则答案为 odd,否则为 even。最后以-1 结束。

Output

输出 x，x 表示存在 01 数串满足前 x 个奇偶条件，但不满足第 x＋1 个条件。假如存在满足 所有条件的 01 串，则输出的数字为问题总数。

Sample Input

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

Sample Output

3

对于 30%的数据，1<=n<=10,0<=number<10

对于 100%的数据，1<=n<=1000000000,0<=number<=5000