Offset Polygons

Background

   One very common geometrical operation in polygon manipulation is finding offset polygons. An offset polygon is obtained by tracing lines, parallel to the original polygon edges, maintaining a given offset distance from them. Here, we are only interested in exterior offset polygons like the one shown in Figure 1, printed in dotted lines. In these circumstances, the offset polygon can be found "to the left" of each original edge, when circulating in the clockwise direction.


Figure 1 - An exterior offset polygon obtained with an offset value of 1.

Problem

   Given an offset value and a sequence of vertices coordinates defining a clockwise closed polygon, the problem is to obtain the correspondent exterior offset polygon. The result must be given as a sequence of vertices coordinates, also in the clockwise direction.
   To simplify the problem, the original polygon is guaranteed to be closed, convex, and limited to 8 vertices. Two consecutive edges are never collinear.

Input

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

   The first line of the input contains the offset value (float format). The second line contains the number of vertices of the original polygon N (integer format). Each one of the following N lines contains two float values, separated by one or more spaces, representing the X and Y coordinates of a vertex. The sequence of vertices is guaranteed to be in the clockwise direction.

Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

   The output must follow the input format (except for the offset value) to represent the exterior offset polygon. The first vertex listed must correspond to the first vertex given.

Sample Input
1

1.0
5
10.0  5.0
10.0  3.0
3.0  3.0
3.0  6.0
5.0  8.0

Sample Output
5
11.000  5.566
11.000  2.000
2.000  2.000
2.000  6.414
4.845  9.259