Bội chung lớn nhất có N chữ số

Cho bốn số nguyên \(A, B, C, N\). Hãy tìm số nguyên dương \(U\) lớn nhất thoả mãn cả hai điều kiện:

• \(U\) là bội chung của \(A\), \(B\) và \(C\) (chia hết cho cả ba số);
• \(U\) có đúng \(N\) chữ số (viết trong hệ thập phân, không có chữ số \(0\) thừa ở đầu).

Nếu không có số \(U\) nào như vậy, in ra \(-1\).

Input

Một dòng chứa bốn số nguyên \(A, B, C, N\).

Output

In ra \(U\) tìm được, hoặc \(-1\) nếu không tồn tại.

Constraints

• \(1 \le A, B, C \le 1000\).
• \(1 \le N \le 18\).

Sample Input 1

6 10 15 3

Sample Output 1

990

Sample Input 2

7 11 13 2

Sample Output 2

-1

Explanation

Ví dụ 1: bội chung nhỏ nhất của \(6, 10, 15\) là \(30\); số \(3\) chữ số lớn nhất chia hết cho \(30\) là \(990\). Ví dụ 2: bội chung nhỏ nhất là \(1001\), không có bội nào có \(2\) chữ số.