{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eHere is a farm. A farmer breeds camels, sheep, and green cockroaches. When a new \r\nanimal is born on the farm, the farmer has to know which kind it is.\r\nHe can recognize cockroaches from other animals himself, but to \r\ndistinguish a camel from a sheep he needs help in the form of a\r\ncommission of experts. The commission measures two parameters of \r\na new-born animal: the hump\u0027s height and the horns\u0027 length.\r\nUsing this data, the experts determine the kind of the animal \r\n(camel or sheep).\r\n\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe decision-making process is the following.\r\nThe \u003ci\u003ei\u003c/i\u003eth expert chooses two integers \u003ci\u003ea\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e \r\nand \u003ci\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e with absolute values not exceeding 2∙10\u003csup\u003e9\u003c/sup\u003e. \r\nFor an animal with parameters (\u003ci\u003eA\u003c/i\u003e, \u003ci\u003eB\u003c/i\u003e), the expert \r\ncalculates the value (\u003ci\u003ea\u003csub\u003ei\u003c/sub\u003eA\u003c/i\u003e + \u003ci\u003eb\u003csub\u003ei\u003c/sub\u003eB\u003c/i\u003e). \r\nIf this value is positive, then the expert decides that this is a \r\ncamel, if the value is negative, then the animal is a sheep, and \r\nif the value is zero, then the expert is at a loss and abstains \r\nfrom voting.\r\n\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe commission makes a decision with respect to each animal by voting.\r\nIf strictly more than half of experts think that the animal is a camel, \r\nthen the commission reports to the farmer that his new animal is a camel.\r\nA similar rule applies to the case when strictly more than half of experts \r\nbelieve that the animal is a sheep. And if the commission cannot identify \r\nthe animal as a camel or a sheep, then the farmer judges that he has \r\none more green cockroach.\r\n\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eOnce the farmer decided that it is too expensive to pay so many \r\nexperts. Indeed, if, for example, the commission consists of four \r\npeople, and the first expert fully agrees with the third one, and \r\nthe second expert makes the same decisions as the fourth expert, \r\nthen there is no sense to keep the third and the fourth experts.\r\nThere are \u003ci\u003eN\u003c/i\u003e confirmed camels and sheep on the farm \r\nalready. The farmer wants to determine the minimal \u003ci\u003eK\u003c/i\u003e\r\nsuch that the commission of \u003ci\u003eK\u003c/i\u003e experts can recognize \r\nall the camels as camels, and all the sheep as sheep\r\n(i.e., there exist pairs of numbers \u003ci\u003ea\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e \r\nand \u003ci\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e such that all the animals on the farm \r\nare recognized by the commission correctly).\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\"\u003eThe first line contains the total number of camels and sheep \r\non the farm \u003ci\u003eN\u003c/i\u003e (1 ≤ \u003ci\u003eN\u003c/i\u003e ≤ 10000). \r\nEach of the next \u003ci\u003eN\u003c/i\u003e lines contains three integers, which \r\ndescribe the \u003ci\u003ej\u003c/i\u003eth animal: \u003ci\u003eA\u003csub\u003ej\u003c/sub\u003e\u003c/i\u003e is the hump\u0027s height,\r\n\u003ci\u003eB\u003csub\u003ej\u003c/sub\u003e\u003c/i\u003e is the horns\u0027 length, and \r\n\u003ci\u003eC\u003csub\u003ej\u003c/sub\u003e\u003c/i\u003e is the kind of the animal (1 denotes a camel and \r\n2 denotes a sheep). \r\n0 ≤ \u003ci\u003eA\u003csub\u003ej\u003c/sub\u003e\u003c/i\u003e, \u003ci\u003eB\u003csub\u003ej\u003c/sub\u003e\u003c/i\u003e ≤ 10000.\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\"\u003eIf there is no commission satisfying the farmer\u0027s requirements, \r\nthen output the number –1. Otherwise, in the first line output\r\nthe minimal number of experts \u003ci\u003eK\u003c/i\u003e, and in the next \u003ci\u003eK\u003c/i\u003e \r\nlines output the numbers \u003ci\u003ea\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e and\r\n\u003ci\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e separated by a space.\r\nYou may output any coefficients such that an expert \r\ncommission using them will make a correct decision with respect \r\nto each of the \u003ci\u003eN\u003c/i\u003e animals.\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\u003e2\r\n10 0 1\r\n0 10 2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n1 -1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}