Find the smallest \(n\)-digit positive integer divisible by \(x\), \(y\), and \(z\).

Input

One line containing \(x\), \(y\), \(z\), and \(n\).

The input satisfies:

• \(1 \le x, y, z \le 10^4\)
• \(1 \le n \le 16\)

Output

Print the required integer, or -1 if it does not exist.

Example

Input

9811 629 5683 1

Output

-1