Mô tả bài toán

Cho một chuỗi s chỉ gồm các chữ cái thường và một số tự nhiên k.

Bạn sẽ thực hiện k bước biến đổi. Ở bước thứ i (1 ≤ i ≤ k), ta xét từng vị trí p trong chuỗi (chỉ số bắt đầu từ 1):

Nếu vị trí p là ước của i (tức là i chia hết cho p), thì ký tự tại vị trí đó sẽ được thay thế bằng chữ cái tương ứng với thứ tự của i trong bảng chữ cái theo quy tắc xoay vòng:

- i = 1 → 'a'

- i = 2 → 'b'

...

- i = 26 → 'z'

- i = 27 → 'a' (quay lại từ đầu)

Yêu cầu

Thực hiện các bước biến đổi từ 1 đến k và in ra chuỗi kết quả cuối cùng.

Dữ liệu nhập vào

Gồm 2 dòng:

- Dòng 1: Số tự nhiên k (1 ≤ k ≤ 10^15)

- Dòng 2: Chuỗi s gồm các chữ cái thường (độ dài ≤ 10^5)

Kết quả ghi ra

Một dòng duy nhất là chuỗi sau khi thực hiện đầy đủ k bước biến đổi.

Ví dụ

Input:
4
abc

Output:
ddc
    

Giải thích:

- Bước 1: Vị trí 1 là ước của 1 → s[1] = 'a' (chuỗi: "abc")

- Bước 2: Vị trí 1, 2 là ước của 2 → s[1] = 'b', s[2] = 'b' (chuỗi: "bbc")

- Bước 3: Vị trí 1, 3 là ước của 3 → s[1] = 'c', s[3] = 'c' (chuỗi: "cbc")

- Bước 4: Vị trí 1, 2, 4 là ước của 4. Chuỗi chỉ có 3 kí tự nên chỉ xét vị trí 1, 2 → s[1] = 'd', s[2] = 'd' (chuỗi: "ddc")