题目描述

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

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

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

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

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

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

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

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

输入格式

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

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

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

输出格式

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

样例

输入样例：

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

输出样例：

3

样例解释

$N=10, M=5$

回答：

1. $S[1 \sim 2]$ 有偶数个 $1$
2. $S[3 \sim 4]$ 有奇数个 $1$
3. $S[5 \sim 6]$ 有偶数个 $1$
4. $S[1 \sim 6]$ 有偶数个 $1$
5. $S[7 \sim 10]$ 有奇数个 $1$

前三个回答可以同时成立，但加入第四个回答时会发生矛盾：

• 前两个回答：$S[1\sim2]$ 偶数，$S[3\sim4]$ 奇数 → $S[1\sim4]$ 奇数
• 第三个回答：$S[5\sim6]$ 偶数 → $S[1\sim6]$ 奇数
• 但第四个回答要求 $S[1\sim6]$ 偶数，矛盾。

所以最小的 $k=3$，即前 $3$ 个回答可以成立，第 $4$ 个回答导致矛盾。

数据范围

• $N \le 10^9$
• $M \le 5000$

时空限制

• 时间限制：1 秒
• 空间限制：64 MB

所有题目已整理完毕。