ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural SU and Orel STU contest. Petrozavodsk training camp. Summer 2006

About     Problems     Submit solution     Judge status     Standings
Contest is over

K. Spy Satellites

Time limit: 2.0 second
Memory limit: 64 MB
Martian spy satellites have taken a photo of an area on the dark side of the Moon. In this photo, only a lot of light points are seen in the dark. The Martian general suggests that the points are secret objects at lunar military bases. He wants to know how many bases there are on the Moon. The Martians suppose that the bases are seen at the photo as clusters of light points and satisfy the following property: the distance between any two objects at the same base is strictly less than the distance from any object at this base to any object at any other base. The area on the photo can be assumed flat, and the distance between objects having in the photo coordinates (A, B) and (С, D) is assumed to be sqrt((AC)2 + (BD)2).

Input

The input contains several tests separated by an empty line. The first line of each test contains the number of objects on the photo N. The next N lines contain coordinates of the objects, two integers separated by a space per line. Absolute values of all coordinates do not exceed 104. After the last test there is an empty line and the number 0. The sum of all N in the input does not exceed 5 000, the sum of all N2 does not exceed 400 000, and the sum of all N3 does not exceed 250 000 000.

Output

For each test, you should output all possible numbers of bases on the photo in the form of a line of length N consisting of zeros and ones. For example, the line 110 means that there may be one or two bases on the photo, and the line 011 means that there may be two or three bases.

Sample

inputoutput
4
-1 -1
1 1
1 -1
-1 1

4
1 0
2 4
1 1
0 1

0
1001
1101
Problem Author: Dmitry Ivankov
Problem Source: Ural SU and Orel STU Contest. Petrozavodsk Summer Session, August 2006
To submit the solution for this problem go to the Problem set: 1478. Spy Satellites