题目描述

小明要计算两个数之和。他得到的第一个数用字符串 s 表示，代表第一个数在 p 进制下的表示。第二个数用字符串 t 表示，代表第二个数在 q 进制下的表示。

对于大于十进制的数，用大写字母 A,B,C,...,Z 表示 10,11,12,⋯,35。

现在给出 p,s,q,t,k，你要写一个程序，将两个数化为十进制后，计算它们的和并以 k 进制形式输出

输入格式

第 1 行，一个正整数 p 和一个字符串 s。

第 2 行，一个正整数 q 和一个字符串 t。

第 3 行，一个正整数 k。

输出格式

一个字符串，表示和在 k 进制下的表示形式。

样例输入

样例输入 1

2 1100101001
16 3FF
8

样例输入 2

21 4D5G9
6 20112333
9

样例输入 3

20 EEDI60
20 IGA6BC4BHH
36

样例输出

样例输出 1

3450

样例输出 2

2680866

样例输出 3

3F019BLV1

提示

第 1 个数是 2 进制 (1100101001)2，转成十进制是 809。

第 2 个数是 16 进制 (3FF)16，转成十进制是 1023。

两数之和等于 1832，转成8进制是 (3450)8

对于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。

16 F
8 7
10

22

36 Z
36 Y
36

1X

8 17
16 F
2

11110