Decorate the Wall

Interview

Time limit1sMemory limit128 MB

Summary

Given non-overlapping axis-aligned rectangles on a wall, find the lowest then leftmost position where a new w' by h' rectangle fits without overlapping any of them, or report failure.

Level: Medium6 of 10
Topics: Geometry, Sorting, Binary search, Intervals
Solved: No attempts yet

Problem

Mr. Rich has just finished building his enormous villa, and the bare interior walls bother him. He decides to hang paintings from his collection, but it quickly becomes hard to find a spot on a wall where a new painting fits without overlapping the ones already hanging.

Write a program that, given the paintings already on a wall, decides where to hang the next painting without moving any existing painting — or reports that it is impossible.

Every painting is an axis-aligned rectangle whose sides are parallel to the edges of the wall, and paintings may not be rotated.

Input

The first line contains the number of test cases.

Each test case begins with a line containing three integers $n$ , $w$ , and $h$ : the number of paintings already on the wall, the width of the wall, and the height of the wall.

Each of the next $n$ lines contains four integers $x_1\ y_1\ x_2\ y_2$ with $0 \le x_1 < x_2 \le w$ and $0 \le y_1 < y_2 \le h$ . The $x$ -coordinates measure the distance from the left edge of the wall and the $y$ -coordinates measure the distance from the bottom edge. $(x_1, y_1)$ is the lower-left corner of a painting and $(x_2, y_2)$ is its upper-right corner.

The last line of the test case contains the size of the next painting to hang: its width $w'$ followed by its height $h'$ ( $1 \le w' \le w$ , $1 \le h' \le h$ ). The painting may not be rotated.

You may assume $0 \le n \le 200$ and $1 \le w, h \le 1000000$ . The paintings already on the wall never overlap one another.

Output

For each test case print one line.

If there is no free spot where the new painting fits without overlapping any existing painting, print Fail!.

Otherwise print the coordinates of the lower-left corner where the painting should be placed, as two integers x y separated by a single space. Two paintings that only touch along an edge or at a corner do not count as overlapping. When more than one placement is possible, choose the one with the smallest $y$ ; if several placements share that smallest $y$ , choose the one with the smallest $x$ .

Examples2

Example 1

Input

Expected output

Fail!
4 0

Example 2
Input
```
1
0 5 5
2 2
```
Expected output
```
0 0
```