Blocks&Balls

A child on a space station plays with a toy called Blocks&Balls. The toy is one rectangular container together with several small rectangular blocks and several balls floating inside it. There is no gravity, so the blocks and the balls stay where they were placed instead of sinking to the bottom.

The child wonders how high the surface would rise after pouring water into the container. Water does not gather at the bottom in orbit, so the experiment is impossible up there, but the level can still be computed.

The base of the container is a rectangle of width $w$ and length $l$, and the container is infinitely tall. The base sits at height $0$. Every block is a rectangular box whose faces are parallel to the faces of the container. A block with center height $z$, width $a$, length $b$ and height $c$ occupies the heights from $z - c/2$ to $z + c/2$, and a horizontal cut through it has area $a \times b$. Every ball has center height $z$ and radius $r$.

You pour water of volume $v$. The water gathers from the bottom, and the blocks and the balls stay fixed, so the part of each object below the surface takes up room the water would otherwise fill. The water level $h$ is the height at which the volume between height $0$ and height $h$, minus the volume the blocks and the balls occupy inside that range, is exactly $v$. Compute $h$.

The first line contains the number of test cases $T$. ($1 \le T \le 20$)

The first line of each test case contains the real numbers $w$, $l$, $v$ and the integers $m$, $n$: the width of the container, its length, the volume of the poured water, the number of blocks and the number of balls. ($0 < w, l \le 1000$, $0 < v \le 10^{12}$, $1 \le m, n \le 100\,000$)

Each of the next $m$ lines contains the real numbers $z$, $a$, $b$, $c$ of one block: the height of its center, its width, its length and its height. ($0 < a \le w$, $0 < b \le l$, $0 < c$, $z - c/2 \ge 0$, $z + c/2 \le 100\,000$)

Each of the next $n$ lines contains the real numbers $z$, $r$ of one ball: the height of its center and its radius. ($0 < 2r \le \min(w, l)$, $z - r \ge 0$, $z + r \le 100\,000$)

Every real number is given with at most six digits after the decimal point. The input is always consistent: no two objects intersect, and every object fits inside the container. The sum of $m + n$ over all test cases is at most $200\,000$.

For each test case, print the water level on its own line, rounded to exactly six digits after the decimal point with the trailing digits written out. If the answer is exactly $3$, print 3.000000.

If several values of $h$ satisfy the condition, print the smallest one. The water level never exceeds $10^6$, and the exact water level is always at least $10^{-7}$ away from the midpoint of two neighboring multiples of $10^{-6}$, so the rounded value is unambiguous.