400398: GYM100162 E Islands

Sergey opened his eyes and found himself in a game. He was on a small island with other boys and girls fighting with wooden swords and trying to capture the neighbouring islands. There were exactly forty islands in the boundless ocean, and each of them was connected with three neighboring islands. The game has only three main rules: not to play after the bridges are raised, not to play in the giveaway and not to look up at the sunset.

When Sergey is so close to panic, he tries to think about mathematical problems. That's why it is not important for him that he can be killed at any moment, who is the author of this book, what is the goal of this silly game and how he can escape. He is focused on the only question: is all that possible from the geometrical point of view? Since Sergey likes generalizations, he came to the following problem.

Consider the archipelago containing n × m islands which are located in all the points with integer coordinates (x, y), 0 ≤ x < n, 0 ≤ y < m. The task is to connect some pairs of the islands with bridges (which are straight segments) in such a way that the following conditions are satisfied:

• every island is connected by bridges with exactly p other islands;
• there is at most one bridge between each pair of islands;
• no bridge passes through islands different from its ends;
• no two bridges intersect in points different from their common end;
• the total length of the bridges is minimal possible.

The input contains several test cases. Each test case consists of three integers n, m and p (1 ≤ n, m ≤ 100, 1 ≤ p ≤ 8) which represent the archipelago sizes and the number of neighbors each island is connected to by bridges.

For each test case, display the case number. Then, if the problem does not have a solution, print "-1". Otherwise, print a real number — the minimum total length of bridges. An absolute or relative error should not exceed 10^- 6. The second line should contain the number of the bridges. The following lines should contain the descriptions of the bridges, one per line. Every bridge should be described by four integers "x₁ y₁ x₂ y₂" which represent the coordinates of the islands connected by the bridge. The order of the bridges and the order of points in each pair are not important. If there are multiple solutions, print any of them.

2 2 2
2 2 3

Case 1: 4.0000000000
4
1 1 1 0
1 1 0 1
1 0 0 0
0 1 0 0
Case 2: -1