Xét một căn nhà có chiều ngang và chiều dài vô cực. Ta biểu diễn căn nhà trên hệ trục Descartes (Đề-các). Trong căn nhà có ~n~ bức tường có được biểu diễn bằng đường thẳng có dạng ~ax + by + c = 0~. Không tồn tại ba bức tường đồng quy tại một điểm. Các bức tường sẽ chia căn nhà thành một số phòng (kể cả các phòng không được bao hoàn toàn bởi các bức tường). Mỗi bức tường sẽ được lắp gương ở đúng một trong hai mặt của bức tường.

Xét hai đường thẳng giao nhau sẽ tạo ra bốn góc, trong đó có hai góc sẽ có một mặt tường và một mặt gương, ta lắp cửa thông nhau tại hai góc này (tức hai phòng chứa hai góc này sẽ có cửa thông nhau).

Sau đó bạn sẽ sơn các căn phòng, và thỏa các điều kiện sau:

• Mỗi phòng được sơn đúng một màu.
• Hai phòng có cửa thông nhau phải có cùng màu.
• Số màu là nhiều nhất có thể.

Bạn cần tìm cách lắp gương sao cho số màu có thể tô cho các phòng là nhiều nhất có thể.

Input

Bạn cần tải về ~10~ file input input_01.txt, input_02.txt, ..., input_10.txt tại đây. Dữ liệu ở mỗi file có dạng:

• Dòng đầu nhập vào ~n~ là số bức tường trong căn nhà.
• ~n~ dòng tiếp theo, mỗi dòng nhập ba số ~a, b, c~ (~|a|, |b|, |c| \le 10^9, a^2 + b^2 > 0, c \neq 0~).

Output

Với mỗi file input_xx.txt, bạn sẽ nộp file output tương ứng output_xx.txt:

• Dòng đầu in ra ~c~ là số màu tô được trong phương án lắp gương của bạn.
• Dòng thứ hai in ra ~n~ số nguyên dương, trong đó, số thứ ~i~ sẽ in ra ~0~ nếu bạn lắp gương ở mặt tường hướng về tâm ~(0, 0)~, ~1~ nếu ngược lại.

Bạn cần nộp toàn bộ file output trong một file zip.

Sample Input

5
-9 39 43
-1 35 -7
-38 49 -47
27 15 10
30 24 5

Sample Output

9
0 0 0 1 0

Subtask

Scoring

Gọi ~J~ là số màu của ban tổ chức tìm được, ~P~ là số màu bạn tìm được, ~T~ là số điểm của test, điểm của bạn trong test được tính như sau: