In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].

If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.

There are two separate, -element sets of points of a two dimensional map: and . None triple of points from the set is collinear. Rockets earth-to-earth are located on points from the set . Enemy objects, which should be destroyed, are located on points from the set . The rockets may fly only in the straight line and their trajectories cannot intersect. We are about to find for each rocket a target to destroy.

Write a program which:

- reads from the standard input coordinates of the points from the sets and ,
- finds the set of pairwise not-intersecting segments, so that one end of each segment belongs to the set , while the other belongs to the set ,
- writes the result to the standard output.

In the first line of the standard input there is written one integer , , equal to the number of elements of the sets and .

In each of the following lines of input one pair of integer numbers from the interval is written. Numbers in each pair are separated by a single space. They are coordinates of the point on a map (first coordinate , then ). The first lines comprise coordinates of the points from the set , the last lines comprise the points from the set . In the -th line there are coordinates of the point , in the -th line there are coordinates of the point , .

The standard output should consist of lines. In the -th line there should be one integer , such that the segment belongs to the set of segments which your program found. (This means that the rocket from the point destroys an object in the point ).

For the input data:

4 0 0 1 5 4 2 2 6 1 2 5 4 4 5 3 1

the correct result is:

2 1 4 3

*Task author: Wojciech Rytter.*