汉娜和亨利要为 $$$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$$$ 英寸。