一天早上,麦片佬发现他所有的麦片片都不见了。他找到了一张纸条而不是它们。原来,他聪明的室友把这些薄片藏在了n个盒子中的一个里。盒子排成一排,从左到右编号为 1 到 n。室友留下诸如“隐藏在第i个盒子的左侧”(“To the left of i”)、“隐藏在第i个盒子的右侧”(“To the right of i”)之类的提示。这些提示意味着第 i 个盒子中也没有碎片。考虑到所有提示,谷物专家想知道他需要检查多少个盒子才能找到谷物片。或者他想找出提示是矛盾的,室友对他撒了谎,也就是说,没有盒子里有薄片。
输入
第一行包含两个整数 n 和 m (1 ≤ n ≤ 1000, 0 ≤ m ≤ 1000),分别代表盒子的数量和提示的数量。接下来的 m 行包含诸如“To the left of i”和“To the right of i”之类的提示,其中 i 是整数 (1 ≤ i ≤ n)。这些提示可能是一致的。
输出
答案应该包含一个整数——必须选中的框的数量,如果提示相互矛盾,则为“-1”。
示例
输入 #1
2 1 To the left of 2
输出 #1
1
输入 #2
3 2 To the right of 1 To the right of 2
输出 #2
1
输入 #3
3 1 To the left of 3
输出 #3
2
输入#4
3 2 To the left of 2 To the right of 1
输出#4
-1