ac

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;


public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception{
        String[] temp = reader.readLine().split(" ");
        String chs = reader.readLine();
        char[] baseChs = chs.toCharArray();
        String arg = reader.readLine();
        int opt = Integer.parseInt(temp[0]);
        // base进制的
        int base = Integer.parseInt(temp[1]);

        Map<Character, Integer> charNumMap = new HashMap<>();
        Map<Integer, Character> numCharMap = new HashMap<>();
        for(int i=0;i<base;i++){
            charNumMap.put(baseChs[i], i+1);
            numCharMap.put(i+1, baseChs[i]);
        }

        if (opt == 1){
            // 数字转字符串
            int n = Integer.valueOf(arg);
            if(n < base){
                System.out.print(numCharMap.get(n));
            }else {
//                System.out.println("n:" + n);
                // n总共需要多少位字符
                int cNums = 1;
                int factor = base;
                int sum = base;
                while (sum < n) {
                    factor *= base;
                    sum += factor;
                    cNums ++;
                }
//                System.out.println("cNUm:" + cNums);
                // 获取对应base，并设置每一个初始都是'A',所得到的和为ASum
                int ASum = 1;
                int[] baseBase = new int[cNums];
                baseBase[0] = 1;
                for(int i=1;i<cNums;i++){
                    baseBase[i] = base * baseBase[i-1];
                    ASum += baseBase[i];
                }
                // 剩下的值然后再去评估
                int left = n - ASum;
                int[] leftAdd = new int[cNums];
                // 评估并构造结果
                for(int i=cNums-1;i>=0;i--) {
                    if (left >= baseBase[i]) {
                        leftAdd[i] = left / baseBase[i];
                        left = left % baseBase[i];
                    }else {
                        leftAdd[i] = 0;
                        continue;
                    }
                }
                // 打印结果
                for(int i=cNums-1;i>=0;i--) {
                    System.out.print(numCharMap.get(1 + leftAdd[i]));
                }
                System.out.println();
            }
        }else {
            // 字符串转数字 O(字符串长度)
            int argLen = arg.length();
            int factor = 1;
            int ans = 0;
            char[] input = arg.toCharArray();
            for(int i = argLen - 1; i >= 0; i--){
                int num = charNumMap.get(input[i]);
                ans += num * factor;
                factor *= base;
            }
            System.out.println(ans);
        }
    }
}

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;


public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception{
        String[] temp = reader.readLine().split(" ");
        String chs = reader.readLine();
        char[] baseChs = chs.toCharArray();
        String arg = reader.readLine();
        int opt = Integer.parseInt(temp[0]);
        int base = Integer.parseInt(temp[1]); // base进制的

        Map<Character, Integer> charNumMap = new HashMap<>();
        Map<Integer, Character> numCharMap = new HashMap<>();
        for(int i=0;i<base;i++){
            charNumMap.put(baseChs[i], i+1);
            numCharMap.put(i+1, baseChs[i]);
        }

        if (opt == 1){
            // 数字转字符串
            int n = Integer.valueOf(arg);
            if(n < base){
                System.out.print(numCharMap.get(n));
            }else {
                int cNums = 1;
                int factor = base;
                int sum = base;
                while (sum < n) {
                    factor *= base;
                    sum += factor;
                    cNums ++;
                }
                int[] baseBase = new int[cNums];
                baseBase[0] = 1;
                for(int i=1;i<cNums;i++){
                    baseBase[i] = base * baseBase[i-1];
                }
                String ans = "";
                for(int i=cNums-1;i>=0;i--){
                    if(n <= 0){
                        break;
                    }
                    int cur = n / baseBase[i];
                    int left = n % baseBase[i];
                    if(left != 0) {
                        char c = numCharMap.get(cur);
                        ans += c;
                        n = left;
                    }else {
                        if(n <= 3){
                            char c = numCharMap.get(n);
                            ans += c;
                            break;
                        }else {
                            cur--;
                            char c = numCharMap.get(cur);
                            ans += c;
                            n = n - cur * baseBase[i];
                        }
                    }
                }
                System.out.print(ans);
            }
        }else {
            // 字符串转数字 O(字符串长度)
            int argLen = arg.length();
            int factor = 1;
            int ans = 0;
            char[] input = arg.toCharArray();
            for(int i = argLen - 1; i >= 0; i--){
                int num = charNumMap.get(input[i]);
                ans += num * factor;
                factor *= base;
            }
            System.out.print(ans);
        }
        System.out.println();
    }
}
/*
1 3
ABC
42

AAAC

2 3
ABC
AAAC

42

1 3
ABC
36

CBC

2 3
ABC
CBC

36
 */