Problem D
Bandit Raids
Three rival gangs of bandits, the Marauders, the Attackers, and the Plunderers, are fighting one another for a limited supply of gold. Each gang has one member for each piece of gold collectively owned by the gang. Every night one gang will raid the hideout of another gang to steal gold. However, in the spirit of inclusivity, one gang may only conduct a raid if every member of the gang can steal one piece of gold from the targeted gang. Thus, a gang with $n$ members can raid a gang with $m$ pieces of gold if and only if $n\leq m$. After a raid, the raiding gang will gain one piece of gold for every member of the gang, and the raided gang will lose one piece of gold for every member of the raiding gang. Bandits are not content to be part of a gang if they do not have their very own piece of gold. So, after a raid, some members of the targeted gang will leave to join the raiding gang such that every bandit has their own piece of gold again. That is, after gang $A$ with $n$ members and $n$ pieces of gold raids gang $B$ with $m$ pieces of gold and $m$ members, gang $A$ will have $2n$ pieces of gold and $2n$ gang members and gang $B$ will have $m-n$ pieces of gold and $m-n$ gang members.
Behind the planning of all raids is one mastermind, Steve. Steve has convinced each of the gangs to trust him, unbeknownst to the others, such that on each night a raid will be conducted at Steve’s direction. Steve has grown tired of the constant fighting and wants to see it end as soon as possible, before the gangs realize that Steve is manipulating them. The fighting will end as soon as one gang has no gold remaining. Help Steve stop the fighting by finding a short sequence of raids that will entirely deplete one gang of its gold.
Input
The input consists of $3$ space-separated positive integers, $a, b, c$, the number of gang members and pieces of gold that the Marauders, the Attackers, and the Plunderers initially have, respectively. It is guaranteed that $1\leq a,b,c \leq 10^{10}$.
Output
On the first line of output, print a single integer, $R$, the number of raids used to reduce one gang’s gold supply to zero (may not be unique). The following $R$ lines of output must describe one such valid sequence of raids. Specifically, the $i$th line should contain $3$ space-separated integers, the number of pieces of gold collectively owned by each of the Marauders, the Attackers, and the Plunderers, respectively, after the raid on the $i$th night (starting with the first night). To avoid suspicion, $R$ must be at most $5\sqrt{a+b+c}$. It can be proven that for any integers $a,b,c$ satisfying $1\leq a,b,c \leq 10^{10}$, there is a sequence of raids for which $R\leq 5\sqrt{a+b+c}$.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 8 2 |
3 6 5 2 4 5 4 8 5 0 |
