Background

路中信息竞赛社的尚炜奇同学在给早培班学弟学妹讲解十六进制与十进制互转时连续出错：

1. 将十六进制 F5 转十进制算成 255（正确答案是 245）
2. 在十进制 245 转十六进制时卡壳
3. 被问"转换后的数是不是回文数"、"245是不是质数"时哑口无言

科创班同学调侃竞赛生的进制转换水平。

Description

题目任务

给定源进制 P、目标进制 Q（2 ≤ P, Q ≤ 16），以及一个合法的 P 进制数字字符串 S（由数字 0-9、大写字母 A-F 组成，A=10，B=11，...，F=15），请完成以下两个任务：

进制转换

将 P 进制字符串 S 转换为 Q 进制字符串 T，要求：

• T 使用数字 0-9、大写字母 A-Z 表示（对应规则同上）
• T 不能包含前导零（若转换结果为 0，仅输出一个 0）
• 注意： S对应的十进制数值不超过unsigned long long的取值范围

输入格式

P Q S

两个十进制的数P和Q，表示源进制与目标进制 一个合法字符串S，表示需要转换的数据

输出格式

1. 第一行：任务1的结果（Q 进制字符串 T）

Format

Input

P Q S 两个十进制的数P和Q，表示源进制与目标进制 一个合法字符串S，表示需要转换的数据

Output

1. 第一行：任务1的结果（Q 进制字符串 T）

Samples

16 10 F5

245

Limitation

样例说明 1

1. 任务 1：十六进制F5转换为十进制是245，无前置零，符合要求；
2. 任务 2：
   • 满足条件 1（P=16且Q=10），输出对应语句；
   • 满足条件 2（S=F5包含5，T=245也包含5），输出对应语句；
   • 不满足条件 3（245不是回文数），故无后续输出。
   • 不满足条件4 （245不是质数），故无后续输出。

1. 2 ≤ P ≤ 16，整数，输入为十进制数字
2. 2 ≤ Q ≤ 16，整数，输入为十进制数字
3. S 为合法的P进制字符串（仅包含大写字母 A-F、数字 0-9）
4. S 对应的十进制数值不超过unsigned long long的最大值
5. 进制转换对应规则：0-9 对应 0-9，A-F 对应 10-15