Hùng vừa được học về số nguyên và hệ đếm. Hùng nói rằng:

• Với mọi số nguyên b>1, ta có một hệ đếm cơ số b
• Các chữ số hợp lệ trong hệ đếm là từ 000 đến b−1
• Chiều dài của một số là số lượng chữ số của nó.
• Độ cao của một số là tổng các chữ số của nó.

Để kiểm tra Hùng, chị gái đưa ra bài toán: Cho một số tự nhiên X trong hệ cơ số b, gồm đúng N chữ số.

Hãy tìm số tự nhiên Y nhỏ hơn X gần nhất (tức là số đứng ngay trước X) sao cho:

• Y có cùng hệ cơ số b
• Y có cùng chiều dài N
• Y có độ cao (tổng chữ số) bằng với X

Nếu không tồn tại số như vậy, in ra số 0.

BIẾT: 

Dữ liệu vào test.inp gồm một dòng duy nhất chứa ba giá trị b N X dạng: b N d1 d2 d3 ... dN

Trong đó:

• 2≤b≤1000
• 2≤N≤10000
• X là số tự nhiên gồm đúng N chữ số trong hệ cơ số b, các số của X ghi cách nhau bởi dấu cách

Dữ liệu ra test.out

• In ra N chữ số của số Y, cách nhau bởi dấu cách
• Nếu không tồn tại Y, in ra: 0