Bordering on Madness

A rectilinear figure is a polygon whose sides all meet at interior angles of 90° or 270° and that contains no holes. A design studio decorates such a figure by drawing one or more rectilinear borders around it. Each border is drawn at a fixed distance $d$ outside the previous border — or outside the original figure, for the first border — in the same right-angle style: every straight run of the outline is pushed outward by $d$ and the corners stay square. The new region enclosed between a border and the previous outline is painted its own color.

A single border is made of one or more closed rectilinear curves. Where the figure has a narrow concavity, the parts of the border advancing along its two facing walls can meet and seal across the mouth of the concavity; the portion of the border trapped inside then becomes a closed curve of its own, disconnected from the rest of the border. So one border may consist of several separate closed curves. The figures are guaranteed to be chosen so that no border ever has two horizontal sections (or two vertical sections) that touch, even at a single point.

For each figure, report — for every border, from the one nearest the figure outward — two values: the length of that border, which is the combined length of all of its closed curves, and the additional area it contributes, which is the area enclosed by that border minus the area enclosed by the previous border (or the figure, for the first border). A pocket that a border seals off counts as a hole in the area that border encloses, so it is not part of the painted region.

The first line contains a single integer $T$, the number of test cases.

Each test case begins with a line containing three positive integers $n$, $m$, and $d$: the number of vertices of the figure ($n \le 100$; a rectilinear polygon has as many vertices as sides), the number of borders to draw ($m \le 20$), and the distance between consecutive borders.

The next $n$ coordinate pairs give the vertices of the figure, each as two positive integers $x$ and $y$. The vertices are listed in clockwise order, starting with the vertex that has the largest $y$ coordinate and, among those, the smallest $x$ coordinate. The coordinate pairs may be split across several lines.

For each test case, print three lines:

1. Case k:, where k is the test case number counting from $1$.
2. Two spaces followed by Perimeters: and then the $m$ border lengths.
3. Two spaces followed by Areas: and then the $m$ additional areas.

In both lists the values appear in order from the border nearest the figure outward, separated by single spaces. Print one blank line between consecutive test cases (but not after the last one).