Cho ba số nguyên dương \(s, d, m (s \le 10^6; d \le 9; m \le 9)\). Hãy tìm ra số nguyên dương \(N\) nhỏ nhất thoả mãn các điều kiện:

• Tổng các chữ số của \(N\) bằng \(s\).
• Các chữ số của \(N\) đều xuất hiện chẵn lần và là tập con của tập các chữ số từ \(0\) đến \(d\) (\(N\) không được bắt đầu bằng chữ số \(0\));
• Số \(N\) chia hết cho \(m\).

Input

• Vào từ thiết bị vào chuẩn gồm một dòng chứa ba số nguyên dương \(s, d, m\).

Output

• Ghi ra thiết bị ra chuẩn một dòng chứa số nguyên dương \(N\) tìm được hoặc ghi số -1 nếu không tồn tại số \(N\) thỏa mãn.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(20\)% số điểm có \(m = 1; s < 100\);
• Subtask \(2\) (\(30\%\) số điểm): \(30\)% số điểm có \(s < 100\);
• Subtask \(3\) (\(30\%\) số điểm): \(30\)% số điểm có \(s < 1000\);
• Subtask \(4\) (\(20\%\) số điểm): \(20\)% số điểm không có rằng buộc gì thêm.

Example

6 5 4

1212