H. Hop, Skip, Jump!
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Welcome one, welcome all, to the Great Penchick Race!

Alice, Bob, and Cindy have started racing their respective penchicks in a three-way parkour race battle. Alice's penchick has already traversed a distance of $$$a$$$ units, Bob's penchick has already traversed a distance of $$$b$$$ units, and Cindy's penchick has already traversed a distance of $$$c$$$ units.

The way the penchicks move is a bit quirky, actually.

  • At the start of each round, one of the contestants chooses a positive integer $$$k$$$.
  • First, one of the penchicks hops and moves forward by $$$k$$$ units.
  • Then, a different penchick skips and moves forward by $$$2k$$$ units.
  • Finally, the remaining penchick jumps and moves forward by $$$3k$$$ units.
Competitive spirit is good, but too much of it can be toxic, especially if the burden of expectations can cause one to dramatically crash out. There are more important things than victory, like fostering friendships and a healthy community.

Thus, Alice and Bob and Cindy agreed to collude such that all three of their penchicks will be equally distant from the starting line, and then end the race there. They can choose the integer $$$k$$$ each round, and also they can decide whose penchicks hop, skip, and jump.

Determine if this task is possible, and if it is, try to achieve it in as few rounds as possible.

Input

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

Each test case consists of a single line containing the three space-separated integers $$$a$$$ and $$$b$$$ and $$$c$$$.

Output

For each test case:

  • If the task is impossible, output a single line containing the integer $$$-1$$$
  • If the task is possible, first, output a line containing the integer $$$n$$$, the number of rounds used in your construction. Then, output the descriptions of these $$$n$$$ rounds, each one described as follows:
    • First, a line containing the positive integer $$$k$$$ for this round. You may choose any positive integer $$$\leq 10^9$$$.
    • Second, a line containing three space-separated integers, some permutation of $$$1$$$ and $$$2$$$ and $$$3$$$, corresponding to a hop, a skip, and a jump, respectively—the first value dictates the motion done by Alice's penchick, the second value dictates the motion done by Bob's penchick, and the third value dictates the motion done by Cindy's penchick.
If the task is possible, it can be shown that $$$100$$$ rounds is always sufficient. If there are multiple possible solutions, any with $$$n \leq 100$$$ will be accepted.
Scoring

There will be exactly one file with $$$T = 10^4$$$ test cases, with $$$1 \leq a, b, c \leq 10^9$$$ in each one; also, it is not the case that $$$a = b = c$$$. If your answer is incorrect on any of the test cases (said yes when it's impossible; said no when it is possible; used too many rounds; proposed a construction doesn't achieve the goal; etc.), you get a $$$0$$$.

Otherwise, you get a higher score the fewer rounds you use (in the cases where the task is possible), with a perfect score if you use the minimal number of rounds in all (possible) test cases.

Let $$$n$$$ be the number of rounds you used in some test case, and let $$$m$$$ be the number of rounds used by the judge.

  • If your solution is correct, you get $$$50$$$ points
  • But if $$$n \leq 2m$$$ in all (possible) test cases (i.e. you never use more than twice the optimal number of rounds, for any test case), you get $$$75$$$ points instead.
  • But if $$$n=m$$$ in all (possible) test cases (i.e. always optimal), you get $$$100$$$ points.

The sample test file is also included (with $$$T=2$$$) but you do not actually need to get it correct in order to get points.

Example
Input
2
15 14 7
1 1 2
Output
4
6
2 1 3
2
3 2 1
5
1 3 2
1
2 1 3
-1
Note

This may not necessarily be the optimal way to answer the first test case.

Still, we see that it is at the very least correct:

  • The penchicks start at distances $$$(15, 14, 7)$$$.
  • After calling $$$k=6$$$, the penchicks are now at distances $$$(27, 20, 25)$$$.
  • After calling $$$k=2$$$, the penchicks are now at distances $$$(33, 24, 27)$$$.
  • After calling $$$k=5$$$, the penchicks are now at distances $$$(38, 39, 37)$$$.
  • After calling $$$k=1$$$, the penchicks are now at distances $$$(40, 40, 40)$$$.