1207: 你猜

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

听了几个答案后，你怀疑朋友的答案可能有错，或说同他之前的答案相互矛盾，例如：$1 - 2$ 奇数，$3 - 4$ 奇数，那么可以确定$1 - 4$ 一定是偶数，如果你的朋友回答是奇数，就产生了矛盾。给出所有你朋友的答案，请你找出第一个出现矛盾的答案

朋友看你在苦思冥想决定给你一点小提示(可跳过)：聪明的你应该很快发现只需要考虑$01$串前缀和$S_i$的奇偶性，即若朋友说$3-4$是偶数，那么$S_2$与$S_4$奇偶性相同，否则相反。那么是不是相同就可以合并，但相反怎么办呢？尝试思考一种合理方式去表征这两种性质。

第一行有两个数字，为 $n$，$Q$ ，表示$01$串长度为$n$，共有$Q$个询问

第$2-Q+1$行每行包括两个数以及一个字符串来描述朋友的回答，$2$个数中间用空格分隔，分别表示区间的起点和终点，后面的字符为"even"（偶数）或"odd"（奇数），表示朋友的答案。

输出仅一行一个数，表示朋友的答案中第一个错误答案的位置，如果所有答案均不矛盾，则输出$-1$。

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

text 20 10 9 16 odd 13 16 even 2 10 even 18 19 even 4 16 even 4 5 odd 1 9 even 8 10 odd 6 16 even 3 6 even

text 4

text 9

对于$30\%$的数据，保证$1 \leq n \leq 10$

对于$60\%$的数据，保证$1 \leq n \leq 1000$

对于$100\%$的数据，保证$2 \leq n \leq 100000$，$2 \leq Q \leq 50000$

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！