P14789 [NERC 2025] Honey Cake

Hannah and Henry are going to host a party for $n$ people, including themselves. They bought a honey cake of size $w \times h \times d$ inches for the party, and want to split it into $n$ equal pieces. The honey cake can be cut parallel to any of its faces. To make cuts precise, each edge of length $w$ is cut into the same number of equal parts, each having integer length; similarly for edges of lengths $h$ and $d$. Given the dimensions of the honey cake, determine whether it is possible to cut it into $n$ equal pieces, and if so, how.

The first line of input contains three integers: $w$, $h$, and $d$, the dimensions of the honey cake in inches ($1 \le w, h, d \le 10^9$). The second line contains a single integer $n$ ($1 \le n \le 10^9$).

Output three integers $w_c$, $h_c$, $d_c$, the number of cuts to be made along each of the dimensions $w$, $h$, and $d$, respectively, if it is possible to cut the cake, or a single integer $-1$ otherwise. Note that making zero cuts along a dimension is allowed, too.

In the first example, the cake will be cut into $5 \cdot 4 \cdot 2 = 40$ pieces of size $2 \times 5 \times 3$ inches. :::align{center}  :::