{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eNow and then you play the following game with your friend. Your friend\r\nwrites down a sequence consisting of zeroes and ones. You choose a\r\ncontinuous subsequence (for example the subsequence from the third to\r\nthe fifth digit inclusively) and ask him, whether this subsequence\r\ncontains even or odd number of ones. Your friend answers your question\r\nand you can ask him about another subsequence and so on. \r\n\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eYour task is\r\nto guess the entire sequence of numbers.\r\nYou suspect some of your friend\u0027s answers may not be correct and you\r\nwant to convict him of falsehood. Thus you have decided to write a\r\nprogram to help you in this matter. The program will receive a series\r\nof your questions together with the answers you have received from\r\nyour friend. The aim of this program is to find the first answer which\r\nis provably wrong, i.e. that there exists a sequence satisfying\r\nanswers to all the previous questions, but no such sequence satisfies\r\nthis answer.\r\n\u003c/div\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eInput contains a series of tests. The first line of each test contains one number, which is\r\nthe length of the sequence of zeroes and ones. This length is less or\r\nequal to 10\u003csup\u003e9\u003c/sup\u003e. In the second line, there is one non-negative integer\r\nwhich is the number of questions asked and answers to them. The number\r\nof questions and answers is less or equal to 5\u0026nbsp;000. The remaining lines\r\nspecify questions and answers. Each line contains one question and the\r\nanswer to this question: two integers (the position of the first and\r\nlast digit in the chosen subsequence) and one word which is either\r\n“\u003ccode\u003eeven\u003c/code\u003e” or “\u003ccode\u003eodd\u003c/code\u003e” (the answer, i.e. the parity of the number of ones in\r\nthe chosen subsequence, where “\u003ccode\u003eeven\u003c/code\u003e” means an even number of ones and\r\n“\u003ccode\u003eodd\u003c/code\u003e” means an odd number). The input is ended with a line containing \u003cnobr\u003e−1\u003c/nobr\u003e.\r\n\u003c/div\u003e\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eEach line of output containing one\r\ninteger \u003ci\u003eX\u003c/i\u003e. Number \u003ci\u003eX\u003c/i\u003e says that there exists a sequence of zeroes and\r\nones satisfying first \u003ci\u003eX\u003c/i\u003e parity conditions, but there exists none\r\nsatisfying \u003ci\u003eX\u003c/i\u003e\u0026nbsp;+\u0026nbsp;1 conditions. If there exists a sequence of zeroes and\r\nones satisfying all the given conditions, then number \u003ci\u003eX\u003c/i\u003e should be the\r\nnumber of all the questions asked.\r\n\u003c/div\u003e\u003c/div\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e10\r\n5\r\n1 2 even\r\n3 4 odd\r\n5 6 even\r\n1 6 even\r\n7 10 odd\r\n-1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}