Block Compaction

You are given a set $R$ of rectangles. Every rectangle is parallel to the $x$ and $y$ axes, and the rectangles are mutually disjoint, although they may touch along boundary edges. All rectangles lie in the quadrant $x \ge 0$, $y \ge 0$.

Compact the rectangles with the procedure COMPACT below. Once the procedure finishes, the position of every rectangle is fixed. Your task is to find the smallest enclosing rectangle that contains all of them. The enclosing rectangle must also be parallel to the $x$ and $y$ axes.

do {
     Step 1. Move blocks downward until no blocks can be moved.
     Step 2. Move blocks leftward until no blocks can be moved.
} Until no blocks can be moved downward or leftward.

The procedure works as follows. Figure 1 is the initial layout of the given rectangles. After moving the blocks downward as far as possible, we obtain the layout in Figure 2.

Figure 1. Input rectangles

Figure 2. After moving the blocks downward

No block can move downward any further in Figure 2, so we move the blocks leftward and obtain Figure 3. Throughout COMPACT the blocks must always stay mutually disjoint, but they may be packed together so that they share boundary edges. See how the groups {E, G, F}, {A, B}, and {C, D} in Figure 2 share boundary edges.

Figure 3. After moving the blocks leftward

Figure 4. After moving the blocks downward again

Repeating the procedure as in Figure 4 until no block can move gives the final compacted layout in Figure 5. The dotted rectangle is the smallest enclosing rectangle.

Figure 5. Applying COMPACT until no block can move yields the smallest enclosing rectangle (the dotted box).

Compute the final enclosing rectangle produced by COMPACT.

Read from standard input. The input consists of $T$ test cases, and the first line contains $T$. The first line of each test case contains $N$ ($1 \le N \le 500$), the number of rectangles. Each of the next $N$ lines describes one rectangle by the integer coordinates of its lower-left vertex $(x, y)$ and its upper-right vertex $(p, q)$, given on a single line as x y p q, where $x < p$, $y < q$, and $0 \le x, y, p, q \le 100000$.

Write to standard output. For each test case, print exactly one line with two numbers $W$ and $H$: the width and the height of the enclosing rectangle produced by COMPACT.