CodeChef October Chellange 2017 : Chef and a great voluntary Program.

Chef likes to eat apples and bananas a lot. Today, he is doing a voluntary service by providing these fruits to needy people in a lunger (a gathering of needy people). The people form a queue to collect fruits from Chef. Chef distributes each person one of the fruits either an apple or a banana.
You are given information about the way Chef distributed fruits to the people by a string s, whose each character is either 'a' or 'b' denoting whether the corresponding person was distributed an apple or a banana.
After the event Chef wants to analyze what he could have done to make the event memorable. The event will be memorable if everyone at the end is happy. Whenever a person in the queue get an apple or a banana then he will observe the most recent K fruits distributed (including fruits he previously took, but not counting the fruit he just got) and if all of them were same as the fruit he just got, then he becomes disgruntled.
The value of K if the person is getting an apple is x, and similarly y for banana.
To make all the people happy, Chef can change the order of distributing the fruits (apple and bananas) and also can give some people extra kiwi fruits. Since the kiwis are costly, Chef would want to minimize the number of kiwis he needed to distribute. Note that a person leaves the queue as soon as Chef distributes him either an apple or a banana. So Chef should provide a person some kiwis before providing an apple or a banana, otherwise Chef won't be able to provide him kiwi as they would have already left the queue.

Help Chef in finding a way of distributing the fruits to the people that make everyone happy and requires Chef to buy as few kiwis as possible.

Input

The first line of the input contains an integer T denoting the number of test cases.
The first line of each test case contains the string s.
The second line contains two space separated integers x, y.

Output

For each test case, output a single string corresponding to the way in which the fruits should be distributed to the people. Apple fruit is denoted by 'a', banana by 'b', and kiwi by '*'. If there are more than one possible solutions, you can print any. Note that the number of apples in the output should be equal to the number of apples in the initial distributions of fruits denoted by string s. Same goes for bananas.

Constraints

• 1 ≤ T ≤ 50
• 1 ≤ |s| ≤ 10⁵
• 1 ≤ x, y ≤ |s|

Subtasks

• Subtask #1 (20 points): x = y = 1
• Subtask #2 (30 points): 1 ≤ |s| ≤ 10³
• Subtask #3 (50 points): Original constraints

Example

Input
6
ab
1 1
aab
1 1
aabb
1 2
aaaaab
2 1
aaaa
1 3
aaaaa
2 2
Output
ab
aba
abba
aa*abaa
a*a*a*a
aa*aa*a

Explanation

Example 1. The way of distributing fruits already makes everyone happy.
Example 2. The second person will be disgruntled as he receives apple same as the person ahead of him. One possible way of having good impression is to distribute in the order aba.
Example 4. It's impossible for the Chef to make everyone happy without buying extra kiwi fruits. Chef will buy one extra kiwi fruit. Now, he distributes aa*abaa, i.e. apple to first and second, kiwi and apple to third, banana to fourth, and apples to fifth and sixth persons. This makes everyone happy. Notice that third person is happy because when he got an apple he checked the last 2 fruits taken which are the apple that the second person and the kiwi that he previously took, and they are not all apples so he is happy.
Example 6. at least two kiwis are needed here, if we gave the first one to third person and second one to fifth person then no one will be disgruntled, for example when the third person get an apple he will check the last two fruits distributed, they are one kiwi given to the same person previously and one apple given the second person so not all of them are apples, so it's fine with him.



SOLUTION:  IN  JAVA.



import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.IOException;
public class ChefVoluntary1 {


    public static void main(String []args) throws IOException {
      
InputStreamReader isr=new InputStreamReader(System.in);
BufferedReader br=new BufferedReader(isr,50);
byte t=Byte.valueOf(br.readLine());
int k=0;

byte i;

String []sf=new String[t];
for(i=0;i<t;i++){
  
int j=0;
String []s2=new String[2];
    BufferedReader br1=new BufferedReader(isr,16*100000);  
  
    String s3=br1.readLine();
  
  
    BufferedReader br2=new BufferedReader(isr,6);
  
StringTokenizer st=new StringTokenizer(br2.readLine()," ");
while(st.hasMoreTokens()){
    s2[j]=st.nextToken();
    j++;
}
    int  a=Integer.parseInt(s2[0]);
 int  b=Integer.parseInt(s2[1]);
  
  

int count1=0,count2=0;

for(int m=s3.length()-1;m>=0;m--){
    if(s3.charAt(m)=='a'){
        count1++;
    }
    if(s3.charAt(m)=='b'){
        count2++;
    }
}

for(int m=s3.length()-1;m>=0;m--){
  
    if(m>-1&&s3.charAt(m)=='a'){
        int count=0;
        for(int l=1;l<=a;l++){
            if((m-l)>-1){
            if(s3.charAt(m-l)==s3.charAt(m)){
                count++;
              
            }}}
            if(count==a){
                int kl=0;
                    if((s3.indexOf('b',0))!=-1&&k!=1){
                        StringBuilder sb=new StringBuilder(s3);
                        char l=s3.charAt(m);char r=s3.charAt(s3.lastIndexOf('b'));
                        sb.setCharAt(m,r);
                        int all=s3.lastIndexOf('b');
                        sb.setCharAt((s3.lastIndexOf('b')),l);
                        s3=sb.toString();
                      
           if(    bb(s3.substring(m,s3.length()),a,b)==false){
                            sb.setCharAt(m,s3.charAt(all));
                            sb.setCharAt(all,s3.charAt(m));
                            s3=sb.toString();
                            k=1;
                            s3=s3.substring(0, m)+"*"+s3.substring(m,s3.length());
                            count=0;
                            m=m-Math.min(a,b)+1;
                        }
                count=0;
  
                }
                    else{
                        s3=s3.substring(0, m)+"*"+s3.substring(m,s3.length());
                    count=0;
                    m=m-Math.min(a,b)+1;
                    }
            count=0;
    }
          
    }
      
  
    if(m>-1&&s3.charAt(m)=='b') {

        int count=0;
        for(int l=1;l<=b;l++){
            if((m-l)>-1&&s3.charAt(m-l)!='a'){
            if(s3.charAt(m-l)==s3.charAt(m)){
                count++;
          
            }
            else
            {
                count=0;
            }
          
            }}
            if(count==b){
                int kl=0;
                if((s3.indexOf('a',0))!=-1&&kl!=1){
                        StringBuilder sb=new StringBuilder(s3);
                        char l=s3.charAt(m);
                        int all=s3.lastIndexOf('a');
                        char r=s3.charAt(all);
                        sb.setCharAt(m,r);
                        sb.setCharAt(s3.lastIndexOf('a'),l);
                        s3=sb.toString();
                        if(    bb(s3.substring(m,s3.length()),a,b)==false){
                          
                            sb.setCharAt(m,s3.charAt(all));
                            sb.setCharAt(all,s3.charAt(m));
                            s3=sb.toString();
                            k=1;
                            s3=s3.substring(0, m)+"*"+s3.substring(m,s3.length());
                            count=0;
                            m=m-Math.min(a, b)+1;
                          
                        }
                    count=0;
              
              
                }
                    else{
                        s3=s3.substring(0, m)+"*"+s3.substring(m,s3.length());
                        count=0;
                        m=m-Math.min(a, b)+1;
                        count=0;
                    }
                    count=0;
                  
            }
        count=0;  
    }
  
}      
      

  
sf[i]=s3;


}
for(String s:sf){
  

System.out.println(s);}
  
    }
    static Boolean bb(String sd,int a,int b){
        Boolean bb=true;
        for(int m=sd.length()-1;m>=0;m--){
          
            if(sd.charAt(m)=='a'){
                int count=0;
                for(int l=1;l<=a;l++){
                    if((m-l)>-1){
                    if(sd.charAt(m-l)==sd.charAt(m)){
                        count++;
                      
                    }}}
                if(count==a){
                bb=false;
                    break;
                }
            }
            if(sd.charAt(m)=='b'){
              
                int count=0;
                for(int l=1;l<=b;l++){
                    if((m-l)>-1){
                    if(sd.charAt(m-l)==sd.charAt(m)){
                        count++;
                      
                    }}}
                if(count==b){
                bb=false;
              
                    break;
                }
            }
      
        }
      
        return bb;      
    }
}