There are two oil pipelines going through Flatland. Each pipeline can be considered as a line on the plane.
Recently the president of Flatland has decided to bring oil to all n cities of Flatland. Therefore he would like to build pipes from each city to one of the pipelines. The minister of industry and education has provided him with data about demand for oil in each city. Transporting a barrel of oil for one kilometer costs 1 flatlar.
The president ordered to connect each city to the closest pipleine, but it turned out that there is one problem. One pipeline belongs to a strong Hrundi Empire, while the other belongs to Bordland Republic. Since president wants to keep good relationships with both countries, he must not give preference to one of the pipelines. That is, if there would be x cities connected to one pipeline and y cities connected to the other, |x - y| must not exceed c .
Help president to decide which city should be connected to which pipeline, so that he keeps his international reputation clean, and spends as few money as possible.
Input
There are mutiple cases in the input file.
The first line of the input file contains n and c (1 <= c <= n <= 200 ). The second line contains the description of the first pipeline --- coordinates of two different points that are lying on it: x1 , y1 , x2 , y2 . The third line describes the second pipeline in the same format.
The following n lines describe cities. Each city is described with three integer numbers: its coordinates and the demand for the oil in thousands of barrels per day (it does not exceed 1000 ).
All coordinates are integer, given in kilometers and do not exceed 104 by absolute values. No two cities coincide. Pipelines do not coincide either.
There is an empty line after each case.
Output
For each city output 1 if it must be connected to the first pipeline, or 2 if it must be connected to the second pipeline.
There should be am empty line after each case.
Sample Input
3 1
0 0 10 0
0 5 7 5
-2 1 1
1 1 1
4 2 10
Sample Output
1 2 1
