你和一个朋友在玩一个游戏：他写一个由0和1组成的序列。你选其中一段（比如第3位到第5位），问他这段里面有奇数个1还是偶数个1，你的朋友回答你的问题，然后你继续问。题目：你的朋友有可能在撒谎。你要检查他的答案，请找出一个x，是的从第一个答案到第x个答案是兼容的，即存在一个序列可以满足它们，但是第x+1个答案和前面的答案不兼容，即不存在一个序列满足从第1个到第x+1个答案。
01序列长度小于等于1000000000，问答个数小于10000.
输入：
第一行一个数N，表示01串的长度。
第二行一个数M，表示问题及答案数。
按下来M行，表示每一个问题及答案。
输出：
一个数表示最后一个不出错的位置(如果没错输出M）。
样例1：
输入：
10
5
1 2 even
3 4 odd
5 6 even
1 6 even
7 10 odd
输出：
3

样例2
输入：
10
5
1 2 even
1 4 even
2 4 odd
1 10 even
3 10 even

输出：
5