Description

Assume two jugs $A$ and $B$, with unlimited water supply. You can use three kinds of operations:

• Fill a jug.
• Empty a jug.
• Pour water from one jug into the other.

When pouring from one jug into the other, you must stop when either the first jug becomes empty or the second jug becomes full. For example, if jug $A$ has capacity $5$ gallons and jug $B$ has capacity $6$ gallons, and the amount of water is $8$ gallons, then when pouring from jug $A$ into jug $B$, jug $B$ becomes full and jug $A$ has $3$ gallons left.

The problem has $3$ parameters: $C_a$, $C_b$, and $N$, which are the capacities of jugs $A$ and $B$ and the target amount $N$, respectively. The goal is to output a sequence of pouring steps so that the amount of water in jug $B$ is exactly $N$.

If there are multiple valid sequences, output any one with the minimum number of operations.

Input Format

The first line contains the number of test cases $T$.

The next $T$ lines each contain three numbers $C_a$, $C_b$, and $N$, as described above.

Constraints: $T \le 30$, $0 < C_a \le C_b$, $N \le C_b \le 1000$, and $C_a$ and $C_b$ are coprime.

Output Format

Print $T$ lines. For each test case, first output the number of operations $a_i$ (a solution is guaranteed to exist). Then output $a_i$ integers, each representing an operation:

• Operation 1: fill A means fill $A$ to full.
• Operation 2: fill B.
• Operation 3: empty A means empty $A$.
• Operation 4: empty B.
• Operation 5: pour B A means pour from $B$ into $A$ (until $A$ is full or $B$ is empty).
• Operation 6: pour A B.

2
3 5 4 
5 7 3 

6 2 5 3 5 2 5 
6 1 6 1 6 4 6 

1
26 29 11

22 1 6 1 6 4 6 1 6 4 6 1 6 4 6 1 6 4 6 1 6 4 6 

Hint

SPJ is enabled.

If your sequence is better than the official answer, it will show UKE. In this case, please contact an administrator to update the testdata.

If your sequence is worse than the official answer, your score will be reduced accordingly.

Translated by ChatGPT 5