Цифры на полу
Таро пытается передать цифры Ханако, выкладывая на полу прямые палочки. Каждую цифру он хочет выразить, создавая одну из форм, показанных на Рисунке 1.
Поскольку у Таро может не быть палочек нужной длины, он не всегда может сделать формы точно такими, как на Рисунке 1. К счастью, Ханако может распознать форму как цифру, если сохраняется связь между палочками в форме. Ни длина палочек, ни направление форм не влияют на восприятие Ханако, пока сохраняется связь. Например, Ханако может распознать все неуклюжие формы на Рисунке 2 как цифры. С другой стороны, Ханако не может распознать формы на Рисунке 3 как цифры. Для ясности, касающиеся палочки слегка раздвинуты на Рисунках 1, 2 и 3. На самом деле, касающиеся палочки пересекаются точно в одной точке.
Рисунок 1: Представление цифр
Рисунок 2: Примеры форм, распознаваемых как цифры
В формах, когда одна палочка касается другой, точка касания является концом хотя бы одной из них. То есть, палочки никогда не пересекаются. Кроме того, угол между такими двумя палочками всегда прямой.
Чтобы Таро мог представлять формы с его ограниченным набором палочек, позиции и длины палочек могут быть изменены, пока сохраняются связи. Также формы могут быть повернуты.
Сохранение связей означает следующее.
Рисунок 3: Формы, не распознаваемые как цифры (такие формы не содержатся в наборе данных)
Разделенные палочки не должны касаться друг друга.
Касающиеся палочки не должны быть разделены.
Когда один конец палочки касается другой палочки, этот конец все еще касается той же палочки. Когда он касается середины другой палочки, он остается касаться середины той же палочки с той же стороны.
Угол между касающимися палочками остается тем же прямым углом (90 градусов и −90 градусов считаются разными, и формы для 2 и 5 остаются различимыми).
Ваша задача — определить, сколько раз каждая цифра появляется на полу.
Формы некоторых цифр всегда содержат формы других цифр. Например, форма для 9 всегда содержит четыре формы для 1, одну форму для 4 и две перекрывающиеся формы для 7. В этой задаче игнорируйте формы, содержащиеся в другой форме, и считайте только цифру "самой большой" формы, составленной из всех взаимосвязанных палочек. Если есть одна форма для 9, это должно быть интерпретировано как одно появление 9 и отсутствие появления 1, 4 или 7.
Входные данные
Входные данные состоят из нескольких наборов данных. Каждый набор данных имеет следующий формат.
n
x_1a y_1a x_1b y_1b
x_2a y_2a x_2b y_2b
...
x_na y_na x_nb y_nb
В первой строке n обозначает количество палочек в наборе данных. В остальных строках каждая строка представляет одну палочку. Четыре целых числа x_a, y_a, x_b, y_b, разделенные пробелами, даны в каждой строке. x_a и y_a — это x- и y-координаты одного конца палочки соответственно. x_b и y_b — это координаты другого конца. Система координат показана на Рисунке 4. Можно предположить, что 1 ≤ n ≤ 1000 и 0 ≤ x_a, y_a, x_b, y_b ≤ 1000.
Конец ввода обозначается строкой, содержащей один ноль.
Рисунок 4: Система координат
Можно также предположить следующие условия.
Более двух палочек не пересекаются в одной точке.
Каждая палочка используется как часть цифры. Нецифровые формы на полу не существуют.
Палочка, составляющая одну цифру, не касается и не пересекает никакую палочку, составляющую другую цифру.
Нет палочки, длина которой равна нулю.
Выходные данные
Для каждого набора данных выведите одну строку, содержащую десять целых чисел, разделенных пробелами. Эти числа представляют, сколько раз 0, 1, 2, ..., и 9 появляются на полу в этом порядке. Строки вывода не должны содержать других символов.