Mèo ~Tesdizz~ đang ngủ trưa thì nghe mùi thơm phát ra từ bếp, cậu liền chạy xuống kiểm tra thử. Thì ra đó là cả một con cá biển thơm ngon, nóng hổi mà chủ nhân cậu mới nấu. Với bản tính ham ăn của mình, ~Tesdizz~ nhảy vọt lên để đớp miếng cá đó. Tuy nhiên chủ nhân của cậu rất ác độc khi đã khóa dĩa cá bằng một câu đố và và cậu phải giải nó để được ăn.
Câu đố cho một số nguyên dương ~X~ có độ dài không quá ~2 \cdot 10^6~ và cho ~Tesdizz~ một số ~K~. Để hoàn thành câu đố này, cậu mèo của chúng ta phải đặt số ~K~ vào một vị trí nào đó trong số ~X~ để số kết quả sau cùng là lớn nhất.
Tuy nhiên với vốn kiến thức lập trình ít ỏi mà ~Tesdizz~ xem lén từ chủ nhân là không đủ để cậu giải được câu đố này. Sức hút khó cưỡng của em cá đã làm cậu mèo của chúng ta phát điên. Hãy giúp mèo ~Tesdizz~ có một bữa ăn ngon nhé.
Dữ liệu vào
- Dòng thứ nhất là hai số nguyên ~N~ ~(1 \le N \le 2 \cdot 10^6 )~ là độ dài của số ~X~ và ~K~ ~(0 \le K \le 9 )~ là số mà ~Tesdizz~ nhận được.
- Dòng thứ hai là số nguyên dương ~X~ có độ dài không quá ~2 \cdot 10^6~.
Kết quả ra
- Một dòng duy nhất là số để giải câu đố.
Chấm điểm
- Có ~50\%~ test tương ứng với ~50\%~ số điểm có ~N \le 10^4~.
- ~50\%~ test còn lại với ~50\%~ số điểm có ~N \le 2 \cdot 10^6~.
Ví dụ 1
Dữ liệu
2 0
12
Kết quả
120
Giải thích
Ta có ~3~ cách chèn số ~0~ vào số ~12~ là:
- ~012~
- ~102~
- ~120~
Và ~120~ là số lớn nhất.
Ví dụ 2
Dữ liệu
6 2
562006
Kết quả
5622006
Giải thích
Ta có ~7~ cách chèn số ~2~ vào số ~562006~ là:
- ~2562006~
- ~5262006~
- ~5622006~
- ~5622006~
- ~5620206~
- ~5620026~
- ~5620062~
Và ~5622006~ là số lớn nhất.
Bình luận