题目描述

Hannah 和 Henry 准备为 $n$ 个人（包括他们自己）举办一场派对。

他们为派对买了一块尺寸为 $w \times h \times d$ 英寸的蜂蜜蛋糕，并想将它切成 $n$ 块相等的部分。蜂蜜蛋糕可以沿着平行于其任一表面的方向切割。为了使切割精确，长度为 $w$ 的每条边被分成相同数量的等份，每份具有整数长度；同样地，长度为 $h$ 和 $d$ 的边也如此。给定蜂蜜蛋糕的尺寸，判断是否可能将其切成 $n$ 块相等的部分，如果可以，请给出切割方案。

输入格式

输入的第一行包含三个整数：$w$、$h$ 和 $d$，表示蜂蜜蛋糕的尺寸（单位：英寸）（$1 \le w, h, d \le 10^9$）。

第二行包含一个整数 $n$ ($1 \le n \le 10^9$)。

输出格式

如果可以切割蛋糕，则输出三个整数 $w_c$、$h_c$、$d_c$，分别表示沿着 $w$、$h$、$d$ 三个维度需要进行的切割次数；否则输出一个整数 $-1$。注意，允许在某个维度上进行零次切割。

10 20 6
40

4 3 1

提示

在第一个例子中，蛋糕将被切成 $5 \cdot 4 \cdot 2 = 40$ 块，每块尺寸为 $2 \times 5 \times 3$ 英寸。

:::align{center} :::