#LX0020. 乒乓球

乒乓球

题目描述

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

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

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

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

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

输入格式

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

接下来一行一个长度为kk的字符串,第ii个字符是A表示第ii局小明赢了,B表示第ii局小红赢了。

输出格式

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

样例输入 #1

20 3
AAB

样例输出 #1

1:0

样例解释 #1

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

样例输入 #2

1000 6
AABBAB

样例输出 #2

24:23

数据范围

对于5%的数据:字符串中只包含A

对于30%的数据:n107n\leq 10^7

对于另外30%的数据:保证无论是谁得分到达1111分时,必定取得这局的胜利。

对于另外15%的数据:保证nnkk的倍数。

对于100%的数据:n1018,k105n\leq 10^{18},k\leq 10^5