Ông Nam có một tin nhắn quan trọng cần chuyển đến các nhân viên của mình. Nội dung tin nhắn là một xâu kí tự gồm chữ cái in thường và in hoa trong bảng chữ cái tiếng Anh. Để bảo mật thông tin, ông Nam đã mã hóa nội dung tin nhắn của mình theo cách sau:

• Ký tự thứ nhất (ký tự đầu tiên) sẽ được đổi thành mã ASCII của nó.
• Ký tự thứ hai: Nếu nó là kí tự in hoa thì dịch chuyển qua phải ~k~ đơn vị theo vòng của bảng chữ cái A...Z. Còn nếu nó là kí tự in thường thì dịch chuyển qua phải ~k - 1~ đơn vị theo vòng của bảng chữ cái a...z.
• Với các ký tự tiếp theo, thực hiện trình tự mã hóa như hai ký tự trên.

Sau khi mã hóa, ông Nam sẽ có được một xâu ~S~ và gửi cho nhân viên.

Ví dụ: Cần nhắn tin HopGap sau khi mã hóa với ~k = 2~ thì xâu ~S~ sẽ là ~S =~ 72p112I97q.

Yêu cầu

Nhận được tin nhắn, các nhân viên đang loay hoay chưa biết giải mã thế nào. Em hãy giúp các nhân viên trong công ty của ông Nam giải mã tin nhắn nhé!

Dữ liệu vào

Gồm hai dòng:

• Dòng thứ nhất: Chứa một xâu ký tự ~S~ khác rỗng có độ dài không quá ~10^5~ ký tự, các kí tự là số và chữ trong bảng chữ cái tiếng Anh.
• Dòng thứ hai: Chứa số nguyên ~k~ ~(1 \le k \le 10^9)~.

Lưu ý, dữ liệu vào nếu các kí tự là số luôn đảm bảo là mã ASCII của các kí tự trong bảng chữ cái tiếng Anh.

Kết quả

Gồm một dòng chứa nội dung tin nhắn sau khi giải mã.

Ràng buộc dữ liệu

• Có 50% số test đầu tiên với xâu ~S~ có độ dài không quá ~10^3~ ký tự.
• Có 50% số test cuối cùng có giới hạn như trong đề.

Ví dụ

Ví dụ 1

INPUT

72p112I97q
2

OUTPUT

HopGap

Ví dụ 2

INPUT

84j101C111q78g119
3

OUTPUT

TheZooNew