Young Liu has recently become obsessed with a puzzle game on his PC called Laser Tank. Some levels are simply too difficult, and after battling for several hours, he decided to ask you, a programming expert, for help. Liu hopes you can write a program to help him clear the levels.

The original game is too complex, so you only need to solve a simplified version here. On the game battlefield (which can be considered a plane), there are $N$ enemy tanks. We can consider each tank to be very small relative to the entire battlefield, effectively a point. At the same time, there are $M$ fence-like obstacles on the battlefield, each of which can be considered a line segment. These line segments do not intersect and do not share any common endpoints. Your task is to destroy all the enemy tanks, and the weapon you have is a laser emitter.

The laser emitter can be placed anywhere on the battlefield (but not on the line segments representing obstacles), and once placed, it cannot be moved. It can fire a laser in any direction. The laser travels in a straight line and cannot pass through fences (though it can pass right along the edge of a fence). When the laser hits a fence, it reflects; in this case, the fence can be treated as a mirror, and the reflection rule is the same as specular reflection.

Any enemy tank hit by the laser (i.e., on the laser's path) will be immediately destroyed. We call the path from the source, following the laser's movement until it hits the target tank, the laser attack path. However, the laser loses energy every time it is reflected by a fence. If the number of reflections exceeds $K$, the laser will no longer have the ability to destroy enemy tanks.

Now, Liu wants you to find a suitable position to place the laser emitter to destroy all the tanks and design the laser direction required to destroy each enemy tank. At the same time, he hopes that under the premise of destroying all enemy tanks, the length of the longest laser attack path is as short as possible, as this is the only way to get a higher score.

This is an "answer-submission" style problem, divided into 10 test cases, stored in: tank1.in ~ tank10.in. Participants do not need to submit a program; they only need to provide the corresponding output files for each data set, tank1.out ~ tank10.out.

Input

The first line of each input file contains two real numbers $C_1, C_2$. They are only used for the scoring of the test case and are irrelevant to the problem itself.

The second line contains three integers, $N, M$, and $K$. Their meanings have already been explained in the problem description.

The next $N$ lines each contain two real numbers $X_i, Y_i$, representing the $X$ and $Y$ coordinates of each enemy tank $i$.

The following $M$ lines each contain four real numbers $X1_i, Y1_i, X2_i, Y2_i$, representing the coordinates of the two endpoints of each fence obstacle.

Output

The first line of the output file is $Ans$, representing the length of the longest laser path.

The second line contains two real numbers $AnsX, AnsY$, representing the position where the laser source is placed.

The following $N$ lines each contain two real numbers $Sx_i, Sy_i$, representing that to destroy enemy tank $i$, a laser must be fired from the source towards the point $(Sx_i, Sy_i)$. That is, the laser direction is $(AnsX, AnsY) \to (Sx_i, Sy_i)$. It is required that the distance between the output point $(AnsX, AnsY)$ and the point $(Sx_i, Sy_i)$ exceeds $0.1$.

Examples

Input 1

1 2
2 1
-4 -4
4 0
1 1 1 -1
-2 2 4 2

Output 1

5.6569
0 0
-4 -4
2 2

Note 1

(In the example above, both attack path lengths are $4\sqrt{2}$)

Scoring

The full score for each data set is 10 points.

For each data set, if any of the following situations occur, the program receives 0 points: 1. No output file. 2. Invalid output. 3. An enemy tank is not destroyed, i.e., the provided solution is not feasible.

Otherwise, your score will be calculated according to the following formula:

$$ Score = \begin{cases} 10 & Ans \le Best \\ C_1 & Ans \times C_2 > Best \\ C_1 + \left\lfloor \frac{(Best - C_2 \times Ans) \times (10 - C_1)}{(1 - C_2) \times Ans} \right\rfloor & C_2 \times Ans \le Best < Ans \end{cases} $$

Implementation Details

This problem provides a checker program (check) to help participants debug. The usage is: ./check X where $X$ is the test case number, from 1 to 10.

If the answer provided in your output file is correct, you will receive the following information: Your output is correct with striking distance Ans, given in the file! where $Ans$ is the answer provided in your output.

If your answer is incorrect, you will receive the following information: Your output is not correct! The tank No.I is not destroyed! and it will prompt you that the $I$-th tank in the input was not destroyed.

If the format of your output file is incorrect, or if the input file has been altered, there is no guarantee that the information output by check will be meaningful.

Note: We guarantee that an output that passes check during debugging will be considered a correct output file during the official testing.

To avoid potential precision issues, the error tolerance used in check is around $10^{-3}$. That is, as long as the tank is sufficiently close to the laser path, it will be considered destroyed.