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≤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.
Dữ liệu
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à cách đó 1 dấu cách là 1 xâu “odd” hay “even”
Kết quả
Thứ tự câu trả lời cuối cùng chưa mâu thuẫn.
Input
5
2
1 2 odd
1 2 even
Output
1
Ràng buộc:
Có 30% số test ứng với 30% số điểm có N≤10;K≤10;
Có 10% số test khác với 10% số điểm có N≤10^9;K≤10;
Có 30% số test khác với 30% số điểm có N≤5000;K≤5000;
Có 20% số test khác với 20% số điểm có N≤10^9;K≤5000;
Có 10% số test còn lại với 10% số điểm có N≤10^9;K≤10^5.
Nguồn: 3D '1920