A和B在玩一个游戏：B编写一个由0和1组成的序列。 A每次选择序列中的一段区间（例如第3位到第5位），询问B这段区间内有奇数个1还是偶数个1。 B回答问题后A继续提问，B可能会撒谎。A需要检查B的答案，找出第一个一定存在问题的回答位置。 回答存在问题的定义：存在至少一个01序列满足该回答之前的所有回答，但不存在任何01序列同时满足该回答及之前的所有回答。

输入描述

1. 第一行一个整数，表示01序列的长度（≤1000000000）
2. 第二行一个整数，表示问答的总个数n
3. 接下来n行，每行描述一个问答：包含两个整数l、r（区间的起止位置）和一个字符串ans，ans为odd表示区间内有奇数个1，为even表示有偶数个1。

输出描述

输出一个整数X：表示存在合法01序列满足前X个回答，但不存在合法序列满足前X+1个回答。如果所有回答都无矛盾，输出总问答个数n。

输入样例

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

输出样例

3