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.

Input

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

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.

Example

Input

10 20 6
40

Output

4 3 1

Note

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.