Problem Description

Little A and Little B are playing a game.

First, Little A writes a sequence S consisting of 0s and 1s, of length N.

Then, Little B asks Little A M questions.

In each question, Little B specifies two numbers l and r, and Little A answers whether there is an odd number of 1s or an even number of 1s in S[l∼r].

Clever Little B suspects that Little A might be lying.

For example, Little A might have answered that S[1∼3] has an odd number of 1s, S[4∼6] has an even number of 1s, but now answers that S[1∼6] has an even number of 1s — this is clearly contradictory.

Your task is to help Little B check these M answers and determine the smallest number k such that the first k answers can be consistent with some 01 sequence S, but the first k+1 answers cannot.

That is, find the smallest k for which there exists a 01 sequence satisfying answers 1 to k, but no sequence satisfies answers 1 to k+1. If all M answers can be satisfied, output M.

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.
Next M lines, each contains a question-answer pair: two integers l and r, and the answer even or odd, indicating whether S[l∼r] has an even or odd number of 1s.

Output Format
Output an integer k, the smallest number such that the 01 sequence satisfies the first k answers but not the first k+1 answers. If all answers are consistent, output M.

Data Range
N ≤ 10⁹, M ≤ 5000

Input Sample:

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

Output Sample:

3