Cho chuỗi ~S~ chỉ chứa các ký tự chữ cái in thường từ a đến z. Thực hiện thao tác sau đây ~K~ lần:

• Chọn một ký tự trong ~S~ và xoay nó sang ký tự tiếp theo trong bảng chữ cái ~(~a xoay thành b, b xoay thành c,...~)~. Lưu ý rằng ký tự tiếp theo của z là a.

Tìm chuỗi có thứ tự từ điển nhỏ nhất có thể tạo ra sau khi thực hiện chính xác ~K~ thao tác.

Input

• Dòng đầu tiên chứa chuỗi ~S~ chỉ bao gồm các ký tự chữ cái in thường (~1 \le |S| \le 10^5~).
• Dòng thứ hai chứa số nguyên ~K~ (~1 \le K \le 10^9~).

Output

• In ra chuỗi có thứ tự từ điển nhỏ nhất có thể tạo ra sau khi thực hiện ~K~ thao tác.

Examples

Sample Input

zyx
3

Sample Output

aax

Scoring

• Subtask ~1~ với ~50\%~ số điểm: \(\lvert S \rvert \le 5\), ~K \le 10~
• Subtask ~2~ với ~50\%~ số điểm: Không có ràng buộc gì thêm

Notes

Trong ví dụ, các thao tác được thực hiện theo thứ tự như sau:

• Xoay ký tự ở vị trí thứ nhất, tạo thành chuỗi ayx.
• Xoay ký tự ở vị trí thứ hai, tạo thành chuỗi azx.
• Xoay ký tự ở vị trí thứ hai, tạo thành chuỗi aax.

Có thể nhận thấy rằng không còn chuỗi nào có thứ tự từ điển nhỏ hơn có thể tạo ra.