题目描述

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

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

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

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

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

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

请你帮助小 B检查这 $M$个答案，并指出在至少多少个回答之后可以确定小 A一定在撒谎。即求出一个最小的 $k$，使得 $01$序列 $S$满足第 $1∼k$个回答，但不满足第 $1∼k+1$个回答。

输入

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

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

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

输出

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

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

3

提示

$N≤10​^9​,M≤5000$