Movers

Time limit1sMemory limit128 MB

Summary

For each box in order, decide whether it can be slid from the open left side to its destination without overlapping placed boxes or walls, and list the rejects.

Level: Hard8 of 10
Topics: Geometry, Simulation, Implementation, Greedy
Solved: No attempts yet

Problem

A manager in charge of a large warehouse expects many boxes to be delivered for storage.

The warehouse is a rectangle whose bottom-left corner is at $(0, 0)$ and whose top-right corner is at $(\text{Depth}, \text{Frontage})$ . Three of its sides are walls; the left side (the one lying along the $y$ -axis) is open.

To move a box to its assigned storage spot, the movers may push it across the warehouse floor, slide it along the side of another box, or carry it without touching any other box or any wall. Boxes are never rotated, and a box must never overlap another box or a wall (merely touching is allowed). Once a box has been set down in its assigned area, it can never be moved again.

If a box cannot be moved to its destination, it is rejected; a rejected box is taken away and does not obstruct the placement of any later box.

Input

The first line contains the number of test cases.

Each test case begins with a line containing three integers $B$ , $\text{Depth}$ , and $\text{Frontage}$ , where $B$ is the number of boxes. Each of the next $B$ lines contains five integers ID X Y W H, separated by single spaces:

ID — a unique identifier for the box
X, Y — the coordinates of the bottom-left corner of the box at its destination
W, H — the width and height of the box

Boxes are processed in the order given.

Constraints:

$0 < B < 200$
$1 < \text{Depth}, \text{Frontage} < 1000000$
$1 < \text{ID} < 1000$
$1 < X, W < \text{Depth}$
$1 < Y, H < \text{Frontage}$

Output

For each test case, output a line beginning with Case followed by the test case number (starting from $0$ ). Then, for every box that cannot be placed, output a line containing Reject and the box's ID, separated by a single space. Rejected boxes must be listed in the same order in which they appear in the input.

Examples3

Example 1

Input

1
5 30 20
7 3 1 8 15
9 24 1 7 3
11 12 14 8 5
13 14 8 10 3
15 15 4 5 3

Expected output

Case 0
Reject 9
Reject 11

Example 2
Input
```
1
1 100 100
2 10 10 20 20
```
Expected output
```
Case 0
```

Example 3

Input

1
1 100 100
5 90 10 20 20

Expected output

Case 0
Reject 5