Description

Alice and Bob are playing a game: Bob writes a sequence consisting of $0$ and $1$. Alice chooses a segment of it (for example, from position $3$ to position $5$) and asks whether this segment contains an odd number of $1$ or an even number of $1$. Bob answers her question, and then Alice continues asking.

Alice wants to check Bob’s answers and determine at which answer Bob must be wrong. “Wrong” means that there exists a $01$ sequence that satisfies all answers before this one, but there does not exist any sequence that satisfies all answers before this one and also this answer.

Input Format

The first line contains an integer $n$, the length of the $01$ sequence.

The second line contains an integer $m$, the number of questions and answers.

Starting from the third line, each line contains one question and its answer. Each line first has two integers indicating the starting position and ending position of the segment you ask about, followed by Bob’s answer. odd means there are an odd number of $1$, and even means there are an even number of $1$.

Output Format

Output one line containing an integer $x$, meaning that there exists a $01$ sequence satisfying answers $1$ through $x$, but there does not exist any sequence satisfying answers $1$ through $x+1$. If none of the answers is wrong, output the total number of answers.

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

3

Hint

For $100\%$ of the testdata, $1 \le n \le 10^9$, $m \le 5 \times 10^3$.

Translated by ChatGPT 5