#A0437. 乒乓球

乒乓球

题目描述

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

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

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

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

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

输入格式

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

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

输出格式

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

20 3
AAB
1:0

样例解释 #1

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

1000 6
AABBAB
24:23

数据范围

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

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

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

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

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