Mật mã hồi tiếp (Feedback Cipher)

Phiên bản: Phước Hưng OJ Extended

Đề bài

Dùng bảng chữ cái thường a..z với giá trị a $=0$, b $=1$, $\ldots$, z $=25$.

Ban đầu khóa hiện tại là $k_1=K$, với $0\le K\le25$. Ở vị trí $i$, gọi $p_i$ là giá trị của ký tự gốc và $c_i$ là giá trị của ký tự đã mã hóa.

Khi mã hóa:

Sau khi xử lý vị trí $i$, khóa được cập nhật bằng:

Khi giải mã, tại vị trí $i$ ta khôi phục:

sau đó khóa tiếp tục được cập nhật bằng chính giá trị $p_i$ vừa khôi phục.

Cho chế độ $M$. Nếu $M=1$, hãy mã hóa xâu $S$. Nếu $M=2$, hãy giải mã xâu $S$. Việc xử lý luôn thực hiện từ trái sang phải.

Input

• Dòng 1 chứa hai số nguyên $M$ và $K$, trong đó $M\in\{1,2\}$ và $0\le K\le25$.
• Dòng 2 chứa xâu $S$ chỉ gồm các chữ cái thường a..z.

Output

In xâu thu được sau khi thực hiện đúng chế độ đã cho.

Subtask

• Subtask 1 (40 điểm): $1\le |S|\le10^3$.
• Subtask 2 (60 điểm): $1\le |S|\le10^6$.

Ví dụ

Ví dụ 1

Input

1 3
hello

Output

kpbnc

Giải thích

Ban đầu $K=3$. Ký tự h có giá trị $7$, nên ký tự mã hóa đầu tiên có giá trị $(7+3)\bmod26=10$, tức k.

Sau đó khóa được cập nhật thành $(3+7+1)\bmod26=11$. Tiếp tục xử lý từ trái sang phải cho các ký tự còn lại, xâu kết quả là kpbnc.

Ví dụ 2

Input

2 3
kpbnc

Output

hello

Giải thích

Ban đầu $K=3$. Ký tự mã hóa k có giá trị $10$, nên ký tự gốc đầu tiên có giá trị $(10-3+26)\bmod26=7$, tức h.

Khóa được cập nhật bằng giá trị ký tự gốc vừa khôi phục. Tiếp tục theo đúng quy tắc, ta thu được xâu hello.