Задача C. Плоттер ≡

Автор:И. Туфанов   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:8 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

Плоттер — устройство для вывода на бумагу чертежей, имеет перо для рисования, которое может перемещаться над бумагой либо в поднятом, либо в опущенном состоянии. При перемещении в опущенном состоянии перо оставляет на бумаге след.

Программа для плоттера требует вывода последовательность отрезков в определённом порядке. Каждый отрезок задан координатами своих вершин M1(x1, y1) и M2(x2, y2). Процесс рисования заключается в следующем: плоттер чертит первый отрезок, потом по прямой передвигает перо к начальной или конечной точке второго отрезка и чертит его. Так продолжается до тех пор, пока все отрезки не будут нарисованы.

Последовательность рисования изменять нельзя, но для каждого отрезка плоттер может определить, рисовать его в направлении от M1 к M2 или от M2 к M1. Поскольку скорость перемещеиня пера ограничена, то для сокращения времени рисования необходимо выбрать для каждого отрезка направление его рисования таким образом, чтобы суммарное передвижение пера было минимальным.

Формат входного файла

Входной файл содержит число N, за которым следует описание N отрезков в том порядке, в каком их и будет рисовать плоттер. Каждому из отрезков соответствует 4 числа x1 y1 x2 y2 — координаты точек M1 к M2 для соответсвующего отрезка. Все числа во входном файле целые.

Формат выходного файла

Выходной файл должен содержать N чисел, разделенных пробелами, где i-е число равно 0, если i-й отрезок следует рисовать от M1 к M2, либо 1, если его следует рисовать от M2 к M1.

Ограничения

1 ≤ N ≤ 100000. Все координаты по модулю не превосходят 10000.

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
2 
0 0 1 1 
3 0 2 1
 
0 1
0.040s 0.012s 15