1237 - True or False?:: HUST Online Judge

1237 - True or False?

Time Limit : 1 Second

Memory Limit : 128 MB

Submission: 228

Solved: 97

Description

You are playing the following game with a AI. AI writes down a sequence consisting of integers. You choose a continuous subsequence (for example the subsequence from the third to the fifth inclusively) and AI will tell you whether the sum of the integers in subsequence you chose is odd or even. And you can ask him about another subsequence and so on. But AI may cheat and tell you a false answer. Your task is to find out the first answer which is provably wrong, i.e. that there exists a sequence satisfying answers to all the previous questions, but no such sequence satisfies this answer.

Because you can't calculate as fast as AI, you have decided to write a program to help in this matter. The program will receive a series of your questions together with the answers you received from AI. And it will tell you the first answer that is provably wrong.

Input

Input contains a series of tests. The first line of each test contains one number, which is the length of the sequence of integers.This length is less or equal to 1,000,000,000. In the second line, there is one non-negative integer which is the number of questions asked and answers to them. The number of questions and answers is less or equal to 5,000. The remaining lines specify questions and answers.Each line contains one question and the answer to this question: two integers (the position of the first and last integer in the chosen subsequence) and one word which is either "even" or "odd" (the answer, i.e. the sum of the integers in the chosen subsequence, where "even" means an even number of sum and "odd" means an odd number). The file is ended with a line containing -1.

Output

Each line of output containing one integer X. Number X says that there exists a sequence of integers satisfying first X answers, but there exists none satisfying first X + 1 answers. If there exists a sequence satisfying all the given answers, then number X should be the number of all the questions asked.

sample input

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

sample output

hint

source