Trong giờ kiểm tra, thầy đã cho các học sinh một bài toán như sau: Cho 3 số nguyên dương S, M, N. Hãy tìm số nguyên dương T nhỏ nhất thỏa mãn các điều kiện sau:

• T > S
• Tổng các chữ số của T trong hệ cơ số M trừ tổng các chữ số của T trong hệ cơ số N bằng 0

Input

• Một dòng duy nhất là 3 số nguyên dương S, M, N với 0 \(\leq\) S \(\leq\) \(10^{16}\), 2 \(\leq\) a < b \(\leq\) 36.

Output

• Một dòng duy nhất là số nguyên dương T trong hệ cơ số 10.

Scoring

• Subtask \(1\) (\(5\%\) số điểm): N = 0
• Subtask \(2\) (\(18\%\) số điểm): N \(\leq\) \(10^{6}\)
• Subtask \(3\) (\(15\%\) số điểm): N \(\leq\) \(10^{12}\)
• Subtask \(1\) (\(62\%\) số điểm): không có giới hạn gì thêm.

Example

10 4 6

18

2174 24 31

2790