Honey Cake

The trap here is that the output asks for cuts, but the math wants parts. If you make $c$ cuts along one dimension, that dimension is split into $c+1$ equal segments. So define:

• $x = w_c + 1$ parts along width
• $y = h_c + 1$ parts along height
• $z = d_c + 1$ parts along depth

For the segment lengths to be integers, we need $x | w$, $y | h$, and $z | d$. The total number of small boxes is $xyz$, so we need $xyz = n$.

That is the whole problem. No geometry boss fight, just divisors wearing a cake costume.

Key Idea

We need to distribute the factors of $n$ among the three dimensions. A dimension can only receive factors that divide its length.

Suppose the remaining number of pieces we still need is $r$. For a dimension of length $L$, the biggest factor of $r$ that can safely go into this dimension is $gcd(L, r)$. Call it $take$.

Set that dimension's part count to $take$, then divide $r$ by $take$.

A tempting thought is to multiply the full volume and test divisibility. Mathematically, that condition is equivalent, but as an implementation plan it is weaker: you still need the actual split, and $w*h*d$ can blast past 64-bit. The gcd construction gives both the proof and the answer.

Why is this greedy okay? Look at one prime $p$. If $p$ appears $e$ times in the current remaining value $r$, and the current dimension contains it $a$ times, this dimension can contribute at most $min(e,a)$ copies of $p$. The gcd takes exactly that many. The remaining copies, if any, literally cannot fit in this dimension, so they must be handled later. There is no downside to taking everything available now; factors are not a budget with weird cross-prime drama.

After all three dimensions, if $r=1$, every factor of the original $n$ was assigned. If $r>1$, some prime factor demand was larger than what $w,h,d$ collectively could provide, so it is impossible.

Algorithm

1. Read $w,h,d,n$.
2. Let $x = gcd(w,n)$, then set $n = n / x$.
3. Let $y = gcd(h,n)$, then set $n = n / y$.
4. Let $z = gcd(d,n)$, then set $n = n / z$.
5. If the remaining $n$ is not $1$, print $-1$.
6. Otherwise print $x-1$, $y-1$, $z-1$.

The sample uses $5 * 4 * 2 = 40$, but our greedy might output $10 * 4 * 1 = 40$ for the same input. That is also valid. Codeforces does not care about aesthetic cake slicing, thank god.

Correctness Proof

Let $r$ be the remaining number of parts that still must be produced before processing some dimension of length $L$.

The algorithm chooses $t = gcd(L,r)$. Therefore $t$ divides $L$, so using $t$ parts along this dimension gives integer segment length. Also $t$ divides $r$, so after setting this part count, the new remaining value $r/t$ is still an integer.

For any prime $p$, let $e$ be its exponent in $r$ and $a$ its exponent in $L$. Any valid choice for this dimension can use at most $min(e,a)$ copies of $p$. The gcd uses exactly $min(e,a)$ copies. Therefore the algorithm leaves exactly the copies of $p$ that cannot be placed in this dimension. This is true independently for every prime.

After processing $w,h,d$, if the remaining value is $1$, then the chosen values $x,y,z$ multiply to the original required $n$, and each divides its corresponding dimension. Thus printing $x-1,y-1,z-1$ gives valid cut counts.

If the remaining value is greater than $1$, then at least one prime factor of the original $n$ still has unassigned exponent after all three dimensions have contributed as much as they possibly can. No valid triple can assign that factor, so the answer is impossible.

So the algorithm is correct.

Complexity

We compute three gcds. Time is $O(log max(w,h,d,n))$, memory is $O(1)$.