Farm 2
Here is a farm. A farmer breeds camels, sheep, and green cockroaches. When a new animal is born on the farm, the farmer has to know which kind it is. He can recognize cockroaches from other animals himself, but to distinguish a camel from a sheep he needs help in the form of a commission of experts. The commission measures two parameters of a new-born animal: the hump's height and the horns' length. Using this data, the experts determine the kind of the animal (camel or sheep).
The decision-making process is the following. The ith expert chooses two integers a_i and b_i, with absolute values not exceeding 2∙10^9. For an animal with parameters (A, B), the expert calculates the value (a_iA + b_iB). If this value is positive, then the expert decides that this is a camel, if the value is negative, then the animal is a sheep, and if the value is zero, then the expert is at a loss and abstains from voting.
The commission makes a decision with respect to each animal by voting. If strictly more than half of experts think that the animal is a camel, then the commission reports to the farmer that his new animal is a camel. A similar rule applies to the case when strictly more than half of experts believe that the animal is a sheep. And if the commission cannot identify the animal as a camel or a sheep, then the farmer judges that he has one more green cockroach.
Once the farmer decided that it is too expensive to pay so many experts. Indeed, if, for example, the commission consists of four people, and the first expert fully agrees with the third one, and the second expert makes the same decisions as the fourth expert, then there is no sense to keep the third and the fourth experts. There are N confirmed camels and sheep on the farm already. The farmer wants to determine the minimal K such that the commission of K experts can recognize all the camels as camels, and all the sheep as sheep (i.e., there exist pairs of numbers a_i and b_i such that all the animals on the farm are recognized by the commission correctly).
Input
The first line contains the total number of camels and sheep on the farm N (1 ≤ N ≤ 10000). Each of the next N lines contains three integers, which describe the j^th animal: A_j is the hump's height, B_j is the horns' length, fnd C_j is the kind of the animal (1 denotes a camel and 2 denotes a sheep). 0 ≤ A_j, B_j ≤ 10000.
Output
If there is no commission satisfying the farmer's requirements, then output the number –1. Otherwise, in the first line output the minimal number of experts K, and in the next K lines output the numbers a_i and b_i separated by a space. You may output any coefficients such that an expert commission using them will make a correct decision with respect to each of the N animals.