0
\$\begingroup\$

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
\$\endgroup\$
  • 3
    \$\begingroup\$ Welcome to CG&CC! This seems like it could be an interesting challenge, but the specification is a bit difficult to understand, and the input format is overly restrictive, not to mention that there's no objective winning criterion. You could make this code-golf, and amend the input format to "anything reasonable" (while describing it in terms of lists or arrays, most likely), to fix the last two issues, but while you're busy with that the challenge should probably remain closed. \$\endgroup\$ – Unrelated String Oct 31 at 21:30
  • 1
    \$\begingroup\$ @CyberDemon I added a visualisation because I think it helps clarify the situation. Please check it both accurately reflects what is going on and is correct. I agree with Unrelated String that the input format should avoid the need for boiler-plate I/O processing (allowing lists in any reasonable format is the norm for a question like this on this site as it allows more languages and keeps the challenge to its core). \$\endgroup\$ – Jonathan Allan Oct 31 at 22:21
  • 1
    \$\begingroup\$ Since there is never a can 0 may we use 0 for "missed" instead of -1? \$\endgroup\$ – Jonathan Allan Oct 31 at 23:49
2
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.