Ultimate Finishing Strike

Saito Hajime is a ninja who must fight many opponents foolish enough to challenge his might. Most of them fall easily to his martial arts, but from time to time Saito faces a particularly powerful and skilled foe. Such a foe appears only after dozens of lesser minions have already been defeated, and the duel always takes place in an empty rectangular room.

To defeat such a foe, Saito performs a special technique called the Zero Stance Ultimate Finishing Strike. He launches a flying kick from his current position. A single kick is not enough against a powerful foe, but Saito can build up power by bouncing off the walls before he lands the hit. Every bounce makes the attack stronger, so with enough bounces any foe can be defeated. Whenever Saito bounces off a wall he obeys the rule that the angle of incidence equals the angle of reflection.

Saito knows exactly how many times he must bounce off the walls to defeat a given foe. He must be careful, though: if the strike takes too long the foe might dodge it, so the total distance Saito travels must be as short as possible.

Given the room, Saito's starting position, the foe's position, and the required number of bounces, determine how many times Saito hits each of the four walls during the shortest possible strike.

The first line contains a single integer: the number of test cases. Each test case consists of three lines:

• A line with three integers $L$, $W$ ($3 \le L, W \le 100$) and $B$ ($0 \le B \le 10^5$): the length and width of the room, and the number of bounces required to defeat the foe.
• A line with two integers $x_S$ and $y_S$ ($0 < x_S < L$, $0 < y_S < W$): Saito's starting coordinates.
• A line with two integers $x_f$ and $y_f$ ($0 < x_f < L$, $0 < y_f < W$): the foe's coordinates.

The bottom-left corner of the room is at $(0, 0)$; the north wall lies in the positive $y$-direction and the east wall in the positive $x$-direction. Saito and the foe never start at the same position. If Saito hits a corner of the room, it counts as two bounces, one for each of the two walls that meet there. Saito may fly over the foe while performing the strike.

For each test case, output:

• One or more lines, each containing four integers: the number of times Saito hits the north, east, south, and west wall, respectively, during a shortest strike that uses exactly $B$ bounces. If several bounce patterns achieve the shortest distance, print every distinct four-tuple, each on its own line, ordered lexicographically (compare the north count first, then east, then south, then west).
• One more line containing the single number $0$.