Bài tập

Xét dãy tăng dần gồm tất cả các số nguyên dương chia hết cho \(A\) hoặc chia hết cho \(B\) (số chia hết cho cả hai chỉ xuất hiện một lần). Hãy tìm số hạng thứ \(N\) của dãy này, gọi là \(U\). Nếu \(U > 10^{18}\) thì in ra \(-1\).

Input

• Một dòng gồm ba số nguyên \(A, B, N\).

Output

• Một số nguyên: \(U\), hoặc \(-1\) nếu \(U > 10^{18}\).

Constraints

• \(1 \le A, B \le 10^9\)
• \(1 \le N \le 10^{15}\)

Sample Input

4 6 10

Sample Output

30

Explanation

Dãy gồm các số chia hết cho \(4\) hoặc \(6\): \(4, 6, 8, 12, 16, 18, 20, 24, 28, 30, \dots\) Số hạng thứ \(10\) là \(30\).

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ố.

Ba số nguyên dương \(a, b, c\) được gọi là bộ ba Pytago nếu bình phương của một trong ba số bằng tổng bình phương của hai số còn lại (thứ tự ba số đưa vào không quan trọng).

Hãy kiểm tra ba số cho trước có phải bộ ba Pytago hay không.

Input

• Một dòng gồm ba số nguyên dương \(a, b, c\).

Output

• In đúng một trong hai dòng sau:
• Ba so da nhap la bo so Pi-ta-go nếu là bộ ba Pytago;
• Ba so da nhap khong la bo so Pi-ta-go nếu không phải.

Constraints

• \(1 \le a, b, c \le 10^9\)

Sample Input 1

6 10 8

Sample Output 1

Ba so da nhap la bo so Pi-ta-go

Sample Input 2

2 3 4

Sample Output 2

Ba so da nhap khong la bo so Pi-ta-go

Sample Input 3

13 5 12

Sample Output 3

Ba so da nhap la bo so Pi-ta-go

Explanation

\(6^2 + 8^2 = 100 = 10^2\) và \(5^2 + 12^2 = 169 = 13^2\), còn \(2^2 + 3^2 = 13 \ne 16 = 4^2\).

Sắn có số nguyên \(a\) và muốn biến nó thành số \(b\) bằng cách áp dụng liên tiếp các phép sau (theo thứ tự tuỳ chọn):

• Phép A: thay số hiện tại \(x\) bằng \(2x\).
• Phép B: viết thêm chữ số \(1\) vào bên phải \(x\), tức là thay \(x\) bằng \(10x + 1\).

Hãy chỉ ra dãy phép biến đổi từ \(a\) đến \(b\), hoặc cho biết không thể. Không cần tối thiểu số phép. (Nếu dãy tồn tại thì nó duy nhất, vì \(2x\) luôn chẵn còn \(10x+1\) luôn tận cùng bằng \(1\).)

Input

• Một dòng gồm hai số nguyên \(a\) và \(b\).

Output

• Nếu không thể, in NO.
• Nếu có thể, in ba dòng: YES; số nguyên \(k\) là số phần tử của dãy; và dãy \(x_1, x_2, \dots, x_k\) trong đó \(x_1 = a\), \(x_k = b\) và mỗi \(x_i\) nhận được từ \(x_{i-1}\) bằng một phép biến đổi.

Constraints

• \(1 \le a < b \le 10^9\).

Sample Input 1

3 1221

Sample Output 1

YES
5
3 6 61 122 1221

Sample Input 2

7 30

Sample Output 2

NO

Sample Input 3

9 361

Sample Output 3

YES
4
9 18 36 361