IITWPC4A - Maggu and Strings

no tags 

Maggu and Coder were playing a game with strings. In each turn of the game, Maggu gives Coder a string. Coder can replace m consecutive 'a' in the string by n consecutive 'b' any number of times. This way he has to create 2 strings, one of maximum possible length and one of minimum possible length.

Input

First line of input contains a single integer T : number of test cases.(1<=T<=100).
For each test case there are exactly two lines.
First line contains a string s (1 <= length(s) <= 10^5) containing letters only from 'a' to 'z'.
Second line contains two space separated integers representing m and n respectively.(1 <= m,n <= 10^5).
Sum of length(s) over all test cases is <= 10^6. 

Output

For each test case, print in a single line containing two space separated integers representing minimum and maximum length of string s that Coder can obtain.

Example

Input:
3
abc
1 2
aa
1 2
aba
1 1 Output: 3 4
2 4
3 3

Explanation

For the first test case, you can convert abc to abc (by not changing at all), bbbc (changing 'a' to 'bb'). minimum length of s is 3 and maximum length is 4.


hide comments
sw2022: 2022-12-23 03:26:03

got 4 WA hahh...

Last edit: 2022-12-23 03:27:45
believec: 2016-12-29 12:34:03

Check for space while looping input string ! 1 wa in 8 test case due to this damn reason !

suraj: 2016-06-18 23:49:47

what is prob in 8 test case, i used long long int also

sarthak gupta: 2015-10-23 15:18:11

got WA because of cin..... use scanf

ASHUTOSH DWIVEDI: 2015-09-01 15:13:13

WA in one go......:(

shantanu tripathi: 2015-08-07 18:09:32

got green in one go!!

pk: 2015-08-02 12:22:32

int cost me 3 wrong answers:)

iharsh234: 2015-07-29 16:44:36

simple one for pythonista!

Bhuvnesh Jain: 2015-07-16 22:26:41

adhoc.

Rydel Dcosta: 2015-07-01 19:57:44

be careful of int overflow..cost me 4 WA :/


Added by:praveen123
Date:2014-01-31
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:IITK ACA CSE online judge