题目描述

在智亦珅泽教育的“算法考古”研究小组中，小珅老师正带领学徒小泽研究一份刚刚出土的远古文明数字铭文。经过初步考证，这份铭文记录了两个庞大数字的加法运算，但由于年代久远，数字的具体进制信息出现了缺失和混乱。

小珅告诉小泽，远古文明广泛使用一种特殊的混合进制记法。在这种记法中，第一个数字由一串字符 $s$ 表示，它原本属于一个 $p$ 进制系统；第二个数字由字符串 $t$ 表示，它原本属于一个 $q$ 进制系统。这两个数字由于某种神秘的对称性，被刻在了同一块石碑上。

为了破译这份铭文，小泽需要编写一个程序，完成以下艰巨的任务：

1. 将第一个字符串 $s$ 从 $p$ 进制还原为现代数学通用的十进制数。
2. 将第二个字符串 $t$ 从 $q$ 进制还原为十进制数。
3. 计算这两个十进制数的和。
4. 最后，将这个和重新编码为一个 $k$ 进制的数，作为最终的密码输出。

输入格式

第 1 行：一个正整数 $p$ 和一个字符串 $s$，用空格隔开。$p$ 表示第一个数的进制，字符串 $s$ 是它在 $p$ 进制下的表示（长度不超过 10）。

第 2 行：一个正整数 $q$ 和一个字符串 $t$，用空格隔开。$q$ 表示第二个数的进制，字符串 $t$ 是它在 $q$ 进制下的表示（长度不超过 10）。

第 3 行：一个正整数 $k$，表示最终输出结果的进制（$2 \le k \le 36$）。

输出格式

一个字符串，表示两个原始数字之和在 $k$ 进制下的表示形式（不含前导零，除非结果为 0）。

2 1100101001
16 3FF
8

3450

21 4D5G9
6 20112333
9

2680866

20 EEDI60
20 IGA6BC4BHH
36

3F019BLV1

数据规模与约定

• 对于 30% 的数据，$2 \le p, q, k \le 10$；
• 对于 40% 的数据，$2 \le p, q \le 10$；
• 对于 100% 的数据，$2 \le p, q, k \le 36$，字符串 $s$ 和 $t$ 只包含数字和大写英文字母，长度不超过 10。