TAP2015C - CompuTenis reloaded

[Due to SPOJ restrictions, this problem has been modified with respect to the original version used in the Argentinian Programming Tournament of 2015 in order to have multiple test cases per input file. The original version of this problem (in Spanish) can be found at http://torneoprogramacion.com.ar/wp-content/uploads/2015/09/pruebaTAP2015.pdf ]

You may remember from a previous edition of TAP about CompuTenis, that sport specially adapted to a public without any mensurable physical qualities and whose rules involve coding with your elbow glued to your ear. This time we will have another problem concerning this exciting subject, in case you found the solution to that one too easy.

Once more, for the purposes of this problem the only thing you have to know about CompuTenis is that two players, which we will call A and B, compete in a match. The match is won by the player who first wins S sets, each set being composed of one or more games. In each set the two players play as many games as is required for one of them to win in at least J games, with a difference of at least D games won in excess of his opponent. The player satisfying both of these conditions is then the winner of the corresponding set.

The Modern Club Association (MCA) has recently found a trove of records of pre-historic CompuTenis matches. Each record consists of a string composed of N characters 'A' or 'B', indicating which player won each of the N games the match had, in the order in which they occurred. Now the MCA wants to know, for each record, what the result of the match was.

Input

There are multiple test cases in the input file. For each test case, the first line contains four integers N, S, J and D. The value N represents the number of games in the record to be analyzed (1 ≤ N ≤ 105). The value S indicates the number of sets a player is required to win in order to win the match (1 ≤ S ≤ 10). The value J is the minimum number of games it is necessary to win in order to win a set, whereas the value D indicates that a player should win at least that number of games more than his opponent in order to win the set (1 ≤ D ≤ J ≤ 100). The second line contains a string composed of N characters 'A' or 'B'. The i-th character of the string indicates which player won the i-th game played in the match. The input string will represent a valid record of a complete match.

Output

For each test case, print a single line containing two integers representing the number of sets won by player A and player B, respectively.

Example

Input:
10 5 2 1
AAAAAAAAAA
21 3 3 2
AABABBBABBBABABABBABB

Output:
5 0
1 3

Added by:Fidel Schaposnik
Date:2015-10-28
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:Argentinian Programming Tournament 2015

hide comments
2016-07-14 13:02:09
can anyone plzz tell the error in id-17281951
2016-07-14 12:57:11
what is the use of s-the number of sets?
2016-06-11 19:56:42 Admin Deepak Baghel
read till EOF very easy.

Last edit: 2016-06-11 19:57:06
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.