题目描述

小 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$