An và Bình chơi trò chơi như sau: An viết một dãy liên tiếp gồm \(N\) số \(0\) hoặc \(1\). Sau đó Bình lần lượt hỏi An các câu hỏi có dạng: Đoạn từ \(i\) đến \(j\) có chẵn số \(1\) hay lẻ số \(1\) (\(i \leq j\)). An sẽ trả lời đoạn từ \(i\) đến \(j\) là chẵn hay lẻ số \(1\). Nhưng sau một số lần hỏi, Bình biết được là An đã không trả lời đúng các câu hỏi của mình.

Yêu cầu

Cho các câu hỏi của Bình và các câu trả lời của An, hãy lập trình giúp Bình tìm ra câu trả lời cuối cùng chưa mâu thuẫn.

Input

• Dòng đầu tiên là số \(N\).
• Dòng thứ hai là số câu hỏi được trả lời \(K\).
• \(K\) dòng sau, mỗi dòng mô tả câu hỏi và trả lời có dạng: hai số nguyên dương \(i, j\) cách nhau một dấu cách và một xâu odd (lẻ) hay even (chẵn).

Output

• Một số nguyên duy nhất là thứ tự câu trả lời cuối cùng chưa mâu thuẫn. Nếu tất cả \(K\) câu trả lời đều không mâu thuẫn, in ra \(K\).

Example

5
2
1 2 odd
1 2 even

1

Scoring

• Có \(30\%\) số test ứng với \(30\%\) số điểm có \(N \leq 10, K \leq 10\).
• Có \(10\%\) số test khác với \(10\%\) số điểm có \(N \leq 10^9, K \leq 10\).
• Có \(30\%\) số test khác với \(30\%\) số điểm có \(N \leq 5000, K \leq 5000\).
• Có \(20\%\) số test khác với \(20\%\) số điểm có \(N \leq 10^9, K \leq 5000\).
• Có \(10\%\) số test còn lại với \(10\%\) số điểm có \(N \leq 10^9, K \leq 10^5\).