P5937 [CEOI 1999] Parity Game

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.

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 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.

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