CF44G Shooting Gallery

Berland amusement park shooting gallery is rightly acknowledged as one of the best in the world. Every day the country's best shooters master their skills there and the many visitors compete in clay pigeon shooting to win decent prizes. And the head of the park has recently decided to make an online version of the shooting gallery. During the elaboration process it turned out that the program that imitates the process of shooting effectively, is needed. To formulate the requirements to the program, the shooting gallery was formally described. A 3D Cartesian system of coordinates was introduced, where the $ X $ axis ran across the gallery floor along the line, along which the shooters are located, the $ Y $ axis ran vertically along the gallery wall and the positive direction of the $ Z $ axis matched the shooting direction. Let's call the $ XOY $ plane a shooting plane and let's assume that all the bullets are out of the muzzles at the points of this area and fly parallel to the $ Z $ axis. Every clay pigeon can be represented as a rectangle whose sides are parallel to $ X $ and $ Y $ axes, and it has a positive $ z $ -coordinate. The distance between a clay pigeon and the shooting plane is always different for every target. The bullet hits the target if it goes through the inner area or border of the rectangle corresponding to it. When the bullet hits the target, the target falls down vertically into the crawl-space of the shooting gallery and cannot be shot at any more. The targets are tough enough, that's why a bullet can not pierce a target all the way through and if a bullet hits a target it can't fly on. In input the simulator program is given the arrangement of all the targets and also of all the shots in the order of their appearance. The program should determine which target was hit by which shot. If you haven't guessed it yet, you are the one who is to write such a program.

N/A

N/A