题目描述

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

首先，小 $\red A$ 写了一个由 $\red 0$ 和 $\red 1$ 组成的序列 $\red S$ ，长度为 $\red N$。

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

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

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

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

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

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

输入格式

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

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

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

输出格式

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

样例

输入样例

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

输出样例

3

提示

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

$\red{M\le 10000}$