← 返回题目列表

Codeforces · 2181/H

H. 蜂蜜蛋糕

中文机器翻译题面 查看原题

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