Two Lights in a Square Room

A large square room holds two point light sources. One is red and the other is green. The room also holds n circular pillars.

Light travels in straight lines and the walls and the pillars absorb it. A pillar lets no light through, so it casts a shadow. Some places in the room get no light at all (black), some get light from exactly one of the two sources (red or green), and some get light from both (yellow). Compute the total area of each of the four colors. The part covered by the pillars counts toward none of the four areas.

The first line contains the number of test cases T.

Each test case is given in this order.

• One line with the coordinates x, y of the red light source.
• One line with the coordinates x, y of the green light source.
• One line with the number of pillars n.
• n lines, each describing one pillar with x, y, r. That pillar is the disk with center (x, y) and radius r.

The room is the square $0 \le x, y \le 100$. The pillars, the walls of the room and the two light sources do not overlap and do not touch.

Limits

• Every number in the input is an integer.
• $1 \le T \le 15$
• $0 \le x, y \le 100$
• $1 \le r \le 49$
• $0 \le n \le 50$

Print five lines for each test case. The first line is Case #X:, where X is the number of the test case, counting from 1. Then print the black, red, green and yellow areas in this order, one per line.

Case #X:
black area
red area
green area
yellow area

Round every area to four digits after the decimal point. Print 0.0000 for an area of zero.