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