Giải bài trực tuyến

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<=N<=10^9) của dãy nhị phân, và cho M (<=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<=A<=B<=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ó tổng các 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ó tổng các 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->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.

Exam1:

Inp:

        10

        5

         1 2 even

         3 4 odd

         5 6 even

         1 6 even

          7 10 odd

Out:

          3