Shooting gallery Puzzle!

Question

Have you been shooting gallery? We are recently.

In our shooting gallery cans and aluminum cans from under various drinks hang and stand. More precisely, they hung and stood.

From our shots, banks dangled from side to side on a rope, were torn off, rang, crumpled. This is not for you to shoot from your fingers.

Each of the bullets either went right through one of the cans, after which the affected can fell to the floor and rolled away so that it was no longer possible to get into it; or didn’t hit any of the cans. In any case, each of the bullets was stuck in the wall behind our target cans.

But that day is past. There was only a wall with bullets stuck in it and a photograph. In an attempt to restore that day and enjoy it again, we collected data on the position of each bullet in the wall, the location of the cans and the order of the shots.

Help determine about each bullet whether it hit one of the cans, and if it hit, then which one.

Input format

The first line contains two integers n and m (1 ≤ m, n ≤ 1000) - the number of cans that were our target on that day, and the number of shots fired that day.

The i-th of the next n lines describes the position of the i-th jar. The position is set by the coordinates of the can’s projection onto the vertical plane. The projection is a rectangle, the sides of which are parallel to the coordinate system applied to this plane. The Y axis of this system is directed vertically upward, and the X axis is horizontally. A rectangle is defined by a pair of points - its left bottom and top right vertices.

It is guaranteed that not a single pair of these rectangles has a single common point.

The i-th of the next m lines describes the position of the i-th bullet in the wall. The bullets are set in the same order in which they left our muzzle. The wall itself is strictly vertical, so we can assume that the position is given by the coordinates of the projection of bullets on a vertical plane. Moreover, the trajectories of the bullets were strictly perpendicular to this plane. The points themselves are defined by a pair of coordinates in the coordinate system already described above.

The distance between the banks and the wall compared to the distance to the shooters is so small that we neglect it.

Output format

In the first and only line print m numbers, the i-th of which says which of the cans the i-th bullet went through, if any. If i didn’t hit any banks, print -1, otherwise print the serial number in the input of the bank, which was struck by the ith bullet.

Sample Input:

4 10
0 0 1 1
2 3 3 8
15 15 20 20
10 12 12 13
2 2
0 -1
23 18
13 12
10 13
16 16
17 17
3 5
3 5
3 3

Sample Output:

-1 -1 -1 -1 4 3 -1 2 -1 -1

Here is a representation of the positions in the above sample - the original locations of the four cans 1 - 4, and the ten bullet locations a - j - note that i is actually in the same location as h ((3,5)) and that a row is shown for y=-1 due to b:

. . . . . . . . . . . . . . . 3 3 3 3 3 3 . . .
. . . . . . . . . . . . . . . 3 3 3 3 3 3 . . .
. . . . . . . . . . . . . . . 3 3 3 3 3 3 . . c
. . . . . . . . . . . . . . . 3 3 g 3 3 3 . . .
. . . . . . . . . . . . . . . 3 f 3 3 3 3 . . .
. . . . . . . . . . . . . . . 3 3 3 3 3 3 . . .
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . e 4 4 . . . . . . . . . . .
. . . . . . . . . . 4 4 4 d . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
. . 2 2 . . . . . . . . . . . . . . . . . . . .
. . 2 2 . . . . . . . . . . . . . . . . . . . .
. . 2 2 . . . . . . . . . . . . . . . . . . . .
. . 2 h . . . . . . . . . . . . . . . . . . . .
. . 2 2 . . . . . . . . . . . . . . . . . . . .
. . 2 j . . . . . . . . . . . . . . . . . . . .
. . a . . . . . . . . . . . . . . . . . . . . .
1 1 . . . . . . . . . . . . . . . . . . . . . .
1 1 . . . . . . . . . . . . . . . . . . . . . .
b . . . . . . . . . . . . . . . . . . . . . . .

Hence e struck 4, f struck 3, and h struck 2 (while g, i, and j would have struck cans if those cans had not already fallen to the floor):

 a  b  c  d  e  f  g  h  i  j
-1 -1 -1 -1  4  3 -1  2 -1 -1

Answer 1

Jelly, (19?) 39 bytes

^{The entire second line is dealing with the strict I/O spec currently in place, while the 19 byte first line is a dyadic Link performing the core of the challenge. Also if 0 were allowed where -1 is currently required save the o- for -2 bytes.}

r/p/ċɗ€ⱮT€Ḣ€ŒQa"$o-
ỴḲ€VḢḢ‘œṖƲŒH€€1¦ç/K

Try it online!