You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小明和小红在打乒乓球比赛。

规则是这样的：对于每一颗球，如果小红赢，小红得一分，如果小明赢，小明得一分。谁的得分首先大于等于 $11$ 分，且比对方的得分高出至少 $2$ 分，则赢得此局比赛。

在记录了 $n$ 颗球的胜负关系后，聪明的裁判员大翼发现：对于任意第 $i(i>k)$ 颗球来说，第 $i$ 颗球的胜负关系，与第 $i-k$ 颗球的胜负关系一模一样。因此，大翼只记录了前 $k$ 颗球的胜负关系。

然而，在记录完毕后，他发现一个重要的问题：他忘记统计两个人分别赢了几局了！

这真是好尴尬啊。还是请你帮他还原一下最终的结果吧！

输入格式

第一行输入 $n,k$，如题所述。

接下来一行一个长度为 $k$ 的字符串，第 $i$ 个字符是 A 表示第 $i$ 局小明赢了，B 表示第 $i$ 局小红赢了。

输出格式

第一行输出两个整数 X:Y，分别表示最后小明/小红赢了几局。

20 3
AAB

1:0

样例解释 #1

最终的序列实际上是 AABAABAABAABAABAABAA，在第 $16$ 颗球结束时，小明和小红的部分是 $11:5$，小明赢得一局。在 $20$ 颗球记录完毕时，当前比分是 $3:1$。

1000 6
AABBAB

24:23

数据范围

对于 $5\%$ 的数据：字符串中只包含 A。

对于 $30\%$ 的数据：$n\leq 10^7$。

对于另外 $30\%$ 的数据：保证无论是谁得分到达 $11$ 分时，必定取得这局的胜利。

对于另外 $15\%$ 的数据：保证 $n$ 是 $k$ 的倍数。

对于 $100\%$ 的数据：$n\leq 10^{18},k\leq 10^5$。