Успадкувати Сфери
У році 2xxx експедиційна команда, приземлившись на планеті, виявила дивні об'єкти, створені давньою цивілізацією, що колись жила на цій планеті. Це прозорі коробки, які містять непрозорі тверді сфери (Рисунок 1). Також було знайдено багато літографій, які, ймовірно, містять інформацію про позиції та радіуси цих сфер.
Рисунок 1. Дивний об'єкт
Спочатку їхнє призначення було невідоме, але професор Замбендорф з'ясував, що перетин, утворений горизонтальною площиною, має важливе значення. Наприклад, перетин об'єкта змінюється, як показано на Рисунку 2, коли площина переміщується знизу вгору.
Рисунок 2. Перетини на різних позиціях
Зрештою, він виявив, що певна інформація виражається через зміни кількості з'єднаних фігур у перетині. Кожна з'єднана фігура є об'єднанням дисків, які перетинаються або торкаються один одного, і кожен диск є перетином відповідної твердої сфери. Наприклад, на Рисунку 2, геометрія якого описана в першому зразку набору даних далі, кількість з'єднаних фігур змінюється як 0, 1, 2, 1, 2, 3, 2, 1, і 0, при z = 0.0000, 162.0000, 167.0000, 173.0004, 185.0000, 191.9996, 198.0000, 203.0000, і 205.0000, відповідно. Призначаючи 1 для збільшення і 0 для зменшення, ці зміни можуть бути виражені 8-бітним двійковим числом 11011000.
Для подальшого аналізу напишіть програму, яка визначає зміни при переміщенні горизонтальної площини знизу (z = 0) вгору (z = 36000).
Вхідні дані
Вхідні дані складаються з серії наборів даних. Кожен набір даних починається з рядка, що містить додатне ціле число, яке вказує кількість сфер N у наборі даних. За ним слідують N рядків, що описують центри та радіуси сфер. Кожен з N рядків містить чотири додатні цілі числа X_i, Y_i, Z_i, і R_i (i = 1, ..., N), що описують центр і радіус i-ї сфери відповідно.
Ви можете припустити, що 1 ≤ N ≤ 100, 1 ≤ R_i ≤ 2000, 0 < X_i - R_i < X_i + R_i < 4000, 0 < Y_i - R_i < Y_i + R_i < 16000, і 0 < Z_i - R_i < Z_i + R_i < 36000. Кожна тверда сфера визначається як множина всіх точок (x, y, z), що задовольняють (x - X_i)^2 + (y - Y_i)^2+ (z - Z_i)^2 ≤ R_i^2.
Сфера може містити інші сфери. Жодні дві сфери не є взаємно дотичними. Кожні Z_i ± R_i і мінімальні/максимальні z координати кола, утвореного перетином будь-яких двох сфер, відрізняються одна від одної щонайменше на 0.01.
Кінець вхідних даних позначається рядком з одним нулем.
Вихідні дані
Для кожного набору даних ваша програма повинна вивести два рядки. Перший рядок повинен містити ціле число M, що вказує кількість переходів. Другий рядок повинен містити M-бітне двійкове число, яке виражає зміни кількості з'єднаних фігур, як зазначено вище.