题目描述

$Bob$ 最近学习了二进制、八进制和十六进制，对于任意 $m$ 进制在做加法时，都是“逢m进一”。

现给定两个位长不超过 $n$ 的 $m（2 \leq m \leq 16）$ 进制数，请在“m进制”下计算这两个数的和。

对于 $m>10$ 时，用‘A’表示 10，用‘B’表示 11，依次类推。

例如十六进制加法，$3F+212=251$，在十六进制下 $F$ 表示15，15+2=17，进位1，个位留下1，过程如下图：

十六进制下的加法

验证一下：3F 和 212 对应十进制是 $(3F)_{16}=3*16+15=(63)_{10}$，$(212)_{16}=2*16^2+1*16+2=530$，$63+530=593$，$251$对应十进制是 $(251)_{16}=2*16^2+5*16+1=(593)_{10}$

输入格式

第一行两个整数，分别表示 $n$ 和 $m$。

第二行一个长度不超过 $n$ 的 $m$ 进制数

第三行一个长度不超过 $n$ 的 $m$ 进制数

输出格式

一行，表示这两个 $m$ 进制的数之和

2 10
12
15

27

5 2
11101
11

100000

4 16
3ABC
11

3ACD

数据规模与约定

$20\%$的测试数据：$1\leq n \leq 30,m=2$

$40\%$的测试数据：$n \leq 18, 2\leq m \leq 10$

$60\%$的测试数据：$n \leq 15, 2\leq m \leq 16$

$100\%$的测试数据：$n \leq 500, 2\leq m \leq 16$