IITWPC4A - Maggu and Strings

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.


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

hide comments
2015-06-18 19:06:02 Insomniac
huhh....
2015-06-18 08:00:06 Ankush
NZEC in python at test case 8. Please check for extra spaces in test cases.
2015-05-25 18:31:36 Rushikesh Potdar
please provide more testcases...
2015-02-19 14:29:16 darol
what is time limit for java?
2015-02-13 07:02:30 swami
java is getting tle should we use fast io
2015-02-01 05:19:12 Arnabjyoti Kalita

Got it...had to check some boundary cases... did not do it...

Last edit: 2015-02-01 05:47:48
2015-01-26 13:44:04 amit vj
wtf..!!...wrong answer @ test case 8.....someone help..
2014-12-28 06:58:55 :.Mohib.:
Not understanding why I am getting wrong answer....anybody plzzz help....some tricky test cases

Reply (numerix): If you need help, use the SPOJ forum.
Because of long long int many wa....Finally AC..Thanks numerix 4 rply....:)

Last edit: 2015-01-17 07:52:52
2014-05-26 16:12:02 Gandalf
One test case fails for int. So use long or long long to be on the safe side
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.