eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Ферма 2

Ферма 2

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Стоїть собі ферма. На фермі сидить фермер і рахує, скільки кого є у нього. Фермер розводить верблюдів, баранів та зелених тарганів. Коли на фермі народжується нова тварина, потрібно визначитиь, хто саме родився. Тарганіов від інших фермер відрізнити зможе і сам, а ось для визначення, верблюд це чи баран, фермер скликав експертну комісію. Комісія вимірює у тварини, що народилась, два параметри — висоту горба та довжину рогів. За циим даними робиться висновок, до якої групи (верблюд чи баран) потрібно віднести тварину.

Експерти діють наступним чином: після скликання комісії i-й експерт вибирає 2 цілих числа a_i та b_i, які по модулю не перевищують 2∙10^9. При народженні нової тварини з параметрами (A, B) експерт обчислює вираз (a_iA + b_iB). Якщо вираз доданій, то експерт приходить до висновку, що тварина — це верблюд, якщо від'ємне, то до висновку, що тварина — це баран. Якщо вираз рівний 0, експерт губиться в здогадках і утримується від яких би то не було суджень.

Вирішення питання по конкретній тварині комісією здійснюється шляхом голосування. Якщо строго більше половини експертів голосує, що тварина — верблюд, то комісія повідомляє фермеру, що на фермі стало одним верблюдом більше. У випадку, якщо більше половини експертів вважаєт тварину бараном, то у книгу робиться запис, що народився баран. Якщо комісія не можеі признати тварину ні верблюдом, ні бараном, то фермер вважає, що народився зелений тарган.

Одного разу фермер вирішив, что накладно оплачивути роботу такій кількості експертів. Дійсно, якщо, наприклад, комісія складається з 4 експертів, при цьому з усіх питань пеший погоджується з третім, а другий — з четвертим, то можна звільнити третього та четвертого експертів, не втративши при цьому у якості роботи комісії. На фермі вже є N верблюдів і баранів (про кожного відомно, верблюд це чи баран). Фермер хоче знайти таке мінімальне K, що комісія з K експертів зможет признати усіх верблюдів верблюдами, а баранів - баранами (тобто кожен з експертів зможе вибрати таку пару чисел a_i та b_i).

Вхідні дані

У першому рядку входу знаходиться число N — загальна кількість верблюдів та баранів на фермі (1N10000). Далі розміщено N рядків, у кожному з яких задано 3 цілих числа — параметри j-ї тварини: A_j — висота горба, B_j — довжина рогів та C_j (1, якщо тварина — верблюд, і 2, якщо баран). 0A_j, B_j10000.

Вихідні дані

Якщо не існуєт комісії, яка задовольняє вимогам фермера, виведіть єдине число, рівне –1. Інакше у першому рядку виведіть шукане число K. У наступних K рядках виведіть через пропуск числа a_i та b_i — величини, якими можуть керуватись експерти при прийнятті рішень. Ви можете вивести довільні коефіцієнти, аби тільки експертна комісія, озброївшись ними, прийняла правильне рішення по кожній з N тварин.

Приклад

Вхідні дані #1
2
10 0 1
0 10 2
Вихідні дані #1
1
1 -1
Автор Олександр Іпатов
Джерело Ural SU and Orel STU Contest. Petrozavodsk Summer Session, August 2006