description: You are given an integer k and a string s that consists only of characters 'a' (a lowercase Latin letter) and '*' (an asterisk).
  
  Each asterisk should be replaced with several (from 0 to k inclusive) lowercase Latin letters 'b'. Different asterisk can be replaced with different counts of letter 'b'.
  
  The result of the replacement is called a BA-string.
  
  Two strings a and b are different if they either have different lengths or there exists such a position i that a_i ≠ b_i.
  
  A string a is lexicographically smaller than a string b if and only if one of the following holds: 
  
    * a is a prefix of b, but a ≠ b; 
    * in the first position where a and b differ, the string a has a letter that appears earlier in the alphabet than the corresponding letter in b. 
  
  
  
  Now consider all different BA-strings and find the x-th lexicographically smallest of them.
  
  Input
  
  The first line contains a single integer t (1 ≤ t ≤ 2000) — the number of testcases.
  
  The first line of each testcase contains three integers n, k and x (1 ≤ n ≤ 2000; 0 ≤ k ≤ 2000; 1 ≤ x ≤ 10^{18}). n is the length of string s.
  
  The second line of each testcase is a string s. It consists of n characters, each of them is either 'a' (a lowercase Latin letter) or '*' (an asterisk).
  
  The sum of n over all testcases doesn't exceed 2000. For each testcase x doesn't exceed the total number of different BA-strings. String s contains at least one character 'a'.
  
  Output
  
  For each testcase, print a single string, consisting only of characters 'b' and 'a' (lowercase Latin letters) — the x-th lexicographically smallest BA-string.
  
  Example
  
  Input
  
  
  3
  2 4 3
  a*
  4 1 3
  a**a
  6 3 20
  **a***
  
  
  Output
  
  
  abb
  abba
  babbbbbbbbb
  
  Note
  
  In the first testcase of the example, BA-strings ordered lexicographically are: 
  
    1. a
    2. ab
    3. abb
    4. abbb
    5. abbbb
  
  
  
  In the second testcase of the example, BA-strings ordered lexicographically are: 
  
    1. aa
    2. aba
    3. abba
  
  
  
  Note that string "aba" is only counted once, even though there are two ways to replace asterisks with characters 'b' to get it.
solution: import java.io.*;
  import java.util.*;
  
  public class Main{
      static int n,k;
      static long x;
      static ArrayList<Integer>arr;
      static ArrayList<Boolean>isa;
  
      static void main() throws Exception{
          n=sc.nextInt();k= sc.nextInt();;x=sc.nextLong();
          char[]in=sc.nextLine().toCharArray();
          arr=new ArrayList<>();
          isa=new ArrayList<>();
          int i=0;
          while(i<in.length){
              if(in[i]=='a'){
                  arr.add(1);
                  isa.add(true);
                  i++;
                  continue;
              }
              int cur=0;
              while(i<in.length && in[i]!='a'){
                  cur+=k;
                  i++;
              }
              arr.add(cur+1);
              isa.add(false);
  
          }
          long[]suffs=new long[arr.size()+1];
          suffs[arr.size()]=1;
          int idx=0;
          for(int j=arr.size()-1;j>=0;j--){
              if(isa.get(j)){
                  suffs[j]=suffs[j+1];
                  continue;
              }
              if(suffs[j+1]>=((x+arr.get(j)-1)/arr.get(j))){
                  idx=j;
                  break;
              }
              suffs[j]=(suffs[j+1]*arr.get(j));
          }
          int[]taken=new int[arr.size()];
          for(int j=0;j<arr.size();j++){
              if(isa.get(j))taken[j]=1;
          }
          while(idx<arr.size()){
              if(isa.get(idx)){
                  idx++;
                  continue;
              }
              for(int take=0;take<arr.get(idx);take++){
                  if(suffs[idx+1]>=((x+take)/(take+1))){
                      taken[idx]=take;
                      long cnts=suffs[idx+1]*(take+1);
                      long dif=cnts-x;
                      x=suffs[idx+1]-dif;
                      break;
                  }
              }
              idx++;
          }
          for(int j=0;j<taken.length;j++){
              while(taken[j]-->0){
                  pw.print(isa.get(j)?'a':'b');
              }
          }
          pw.println();
      }
      public static void main(String[] args) throws Exception{
          sc=new MScanner(System.in);
  //		sc=new MScanner(" .in");
          pw = new PrintWriter(System.out);
          int tc=1;
          tc=sc.nextInt();
          for(curt=1;curt<=tc;curt++) {
  //			pw.printf("Case #%d:", curt);
              main();
          }
          pw.flush();
      }
      static int curt;
      static PrintWriter pw;
      static MScanner sc;
      static class MScanner {
          StringTokenizer st;
          BufferedReader br;
          public MScanner(InputStream system) {
              br = new BufferedReader(new InputStreamReader(system));
          }
  
          public MScanner(String file) throws Exception {
              br = new BufferedReader(new FileReader(file));
          }
  
          public String next() throws IOException {
              while (st == null || !st.hasMoreTokens())
                  st = new StringTokenizer(br.readLine());
              return st.nextToken();
          }
          public int[] intArr(int n) throws IOException {
              int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
              return in;
          }
          public long[] longArr(int n) throws IOException {
              long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
              return in;
          }
          public int[] intSortedArr(int n) throws IOException {
              int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
              shuffle(in);
              Arrays.sort(in);
              return in;
          }
          public long[] longSortedArr(int n) throws IOException {
              long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
              shuffle(in);
              Arrays.sort(in);
              return in;
          }
          public Integer[] IntegerArr(int n) throws IOException {
              Integer[]in=new Integer[n];for(int i=0;i<n;i++)in[i]=nextInt();
              return in;
          }
          public Long[] LongArr(int n) throws IOException {
              Long[]in=new Long[n];for(int i=0;i<n;i++)in[i]=nextLong();
              return in;
          }
          public String nextLine() throws IOException {
              return br.readLine();
          }
  
          public int nextInt() throws IOException {
              return Integer.parseInt(next());
          }
  
          public double nextDouble() throws IOException {
              return Double.parseDouble(next());
          }
  
          public char nextChar() throws IOException {
              return next().charAt(0);
          }
  
          public long nextLong() throws IOException {
              return Long.parseLong(next());
          }
  
          public boolean ready() throws IOException {
              return br.ready();
          }
  
          public void waitForInput() throws InterruptedException {
              Thread.sleep(3000);
          }
  
      }
      static void dbg(int[]in) {
          System.out.println(Arrays.toString(in));
      }
      static void dbg(long[]in) {
          System.out.println(Arrays.toString(in));
      }
      static void sort(int[]in) {
          shuffle(in);
          Arrays.sort(in);
      }
      static void sort(long[]in) {
          shuffle(in);
          Arrays.sort(in);
      }
      static void shuffle(int[]in) {
          for(int i=0;i<in.length;i++) {
              int idx=(int)(Math.random()*in.length);
              int tmp=in[i];
              in[i]=in[idx];
              in[idx]=tmp;
          }
      }
      static void shuffle(long[]in) {
          for(int i=0;i<in.length;i++) {
              int idx=(int)(Math.random()*in.length);
              long tmp=in[i];
              in[i]=in[idx];
              in[idx]=tmp;
          }
      }
  }