题目描述

蛇年跨年庆典推出了二进制数字寻宝活动，参与者需破解数字密码赢取新年礼品。活动规则如下：给定两个正整数n和k（k≥1，最低位为二进制第1位），需在1到n的所有整数中，筛选出二进制表示中第k位为1的所有数字，计算这些数字的乘积后，对乘积进行质因数分解，最终按质因数从小到大的顺序输出每个质因子及其对应的指数。

例如：

• 当n=10、k=2时，1-10中二进制第2位为1的数是2、3、6、7、10，它们的乘积为2×3×6×7×10=2520；
• 2520的质因数分解结果为2³×3²×5¹×7¹，因此输出对应质因子和指数。

输入格式

第一行包含两个正整数n和k，分别表示数字范围上限和二进制位数（k≥1）。

输出格式

按质因数从小到大的顺序，每行输出一个质因子及其指数，格式为“质因子:指数”。 如果没有质因子，不输出内容

输入输出样例 #1

输入 #1

10 2

输出 #1

2:3
3:2
5:1
7:1

数据规模

• 对于20%的测试点：n≤100，k≤5；
• 对于100%的测试点：n≤10⁵，k≤20。

样例解释

• 输入n=10、k=2（二进制第2位，最低位为第1位），需筛选二进制第2位为1的数：2（10）、3（11）、6（110）、7（111）、10（1010）；
• 计算乘积：2×3×6×7×10=2520；
• 2520分解质因数为2³×3²×5¹×7¹，按从小到大顺序输出每个质因子及其指数。