Submit solution

Points: 0.93 (partial)
Time limit: 3.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
CEOI 1999
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Trong buổi đầu tiên học đội tuyển, thầy giáo đã cho học sinh làm quen với một bài toán đơn giản - bài toán về số nhị phân. Và để tăng thêm phần hứng thú cho học sinh của mình, thầy đã ra cho học sinh một trò chơi về dãy nhị phân.

Thầy giáo sẽ cho độ dài ~N~ (~1 \le N \le 10^{9}~) của dãy nhị phân, và cho ~M~ (~\le 5000~) câu trả lời về dãy nhị phân này, mỗi câu trả lời có dạng ~A~ ~B~ ~st~, trong đó ~1 \le A \le B \le N~ và st là ~1~ xâu kí tự 'odd' hoặc 'even'. st='odd' cho chúng ta biết đoạn từ ~A~ đến ~B~ trong dãy nhị phân có số số bit ~1~ là số lẻ, st='even' cho chúng ta biết đoạn từ ~A~ đến ~B~ trong dãy nhị phân có số số bit ~1~ là số chẵn.

Các câu trả lời của thầy sẽ được đưa ra theo thứ tự, và học sinh phải trả lời cho thầy giáo số nguyên ~X~ lớn nhất, sao cho tồn tại ~1~ xâu nhị phân độ dài ~N~ thỏa mãn các câu trả lời từ ~1 \rightarrow X~ của thầy giáo.

Input

Dòng thứ nhất số nguyên dương ~N~ - độ dài của xâu nhị phân.

Dòng thứ hai số nguyên ~M~ - số câu trả lời của thầy giáo.

~M~ dòng tiếp theo chứa ~M~ câu trả lời của thầy theo định dạng như trong đề bài (thứ tự các câu trả lời của thầy giáo chính là thứ tự đưa ra trong input).

Output

In ra một số nguyên là câu trả lời của học sinh.

Sample Input

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

Sample Output

3

Comments

Please read the guidelines before commenting.


There are no comments at the moment.