#150. 奇偶游戏

奇偶游戏

题目描述

A\red A 和小 B\red B 在玩一个游戏。

首先,小 A\red A 写了一个由 0\red 01\red 1 组成的序列 S\red S ,长度为 N\red N

然后,小 B\red B 向小 A\red A 提出了 M\red M 个问题。

在每个问题中,小 B\red B 指定两个数 l\red lr\red r,小 A\red A 回答 S[lr]\red{S[l\sim r]} 中有奇数个 1\red 1 还是偶数个 1\red 1

机智的小 B\red B 发现小 A\red A 有可能在撒谎。

例如,小 A\red A 曾经回答过 S[13]\red{S[1\sim 3]} 中有奇数个 1\red 1S[46]\red{S[4\sim 6]} 中有偶数个 1\red 1,现在又回答 S[16]\red{S[1\sim 6]} 中有偶数个 1\red 1,显然这是自相矛盾的。

请你帮助小 B\red B 检查这 M\red M 个答案,并指出在至少多少个回答之后可以确定小 A\red A 一定在撒谎。

即求出一个最小的 k\red k,使得 01\red{01} 序列 S\red S 满足第 1k\red{1\sim k}个回答,但不满足第 1k+1\red{1\sim k+1} 个回答。

输入格式

第一行包含一个整数 N\red N ,表示 01\red{01} 序列长度。

第二行包含一个整数 M\red M ,表示问题数量。

接下来 M\red M 行,每行包含一组问答:两个整数 l\red lr\red r,以及回答“even”或“odd”,用以描述 S[lr]\red{S[l\sim r]} 中有奇数个 1\red 1 还是偶数个 1\red 1

输出格式

输出一个整数 k\red k,表示 01\red{01} 序列满足第1k\red{1\sim k}个回答,但不满足第 1k+1\red{1\sim k+1}个回答,如果 01\red{01} 序列满足所有回答,则输出问题总数量。

样例

输入样例

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

输出样例

3

提示

N109\red{N\le 10^9} ,

M10000\red{M\le 10000}