***Smriti and the Strings( DELETE K CHARACTERS FROM THE STRING AND RESULTING STRING MUST BE LEXOGRAPHICALY BIGGEST )

Smriti and the Strings

Smriti is learning about strings in school and asks her best friend, Stephanie, to give her a practice problem.

Stephanie gives Smriti a string S$S$ of length n$n$, and a positive integer m$m$ (where m<n$m<n$). Smriti must delete exactly m$m$ characters from the String such that the resultant string is lexicographically largest (last when ordered alphabetically). Solve the challenge along with Smriti so she can check her answer!

Input Format

The first line contains an integer, T$T$, the number of test cases.
Each of the T$T$ subsequent lines of test cases contains 2$2$ space-separated values: a string, S$S$, followed by an integer, m$m$.

Constraints

• 1≤T≤1000$1\le T\le 1000$
• 1≤N≤106$1\le N\le {10}^6$
• 1≤∑ni≤107$1\le \sum n_i\le {10}^7$ where ni$n_i$ is the length of the ith$i^{th}$ string.
• 1≤m<n$1\le m<n$
• All strings contain only lowercase letters.

Output Format

For each line i$i$ of the T$T$ test cases (where 0≤i<T$0\le i<T$), print the lexicographically largest string that can be formed by deleting mi$m_i$ characters from Si$S_i$ on a new line.

Sample Input

2
abcde 2
dcabe 2

Sample Output

cde
dce

Explanation

Test Case 0:
S0="abcde", m=2$S_0=\text{"abcde", }m=2$
We delete the first 2$2$ characters to get cde$\text{cde}$, the lexicographically largest possible string.

Test Case 1:
S1="dcabe", m=2$S_1=\text{"dcabe", }m=2$ We delete the 3rd$3^{rd}$ and 4th$4^{th}$ characters to get "dce"$\text{"dce"}$, the lexicographically largest possible string.

----------------------------------EDITORIAL-------------------------------------------------

THIS PROBLEM CAN BE SOLVED  USING  STACK, OR SEGMENT TREE , I USED SEG TREE

   WE HAVE TO MAXIMIZE THE VALUE OF   msb CHARACTERS FIRST , SO SUPPOSE WE HAVE  D OPERATION REMAINING AND ANY CHARACTERS FROM MSB TO MSB+D TH CHARACTER   IS GREATER THAN THE MSB CHARACTER    WE CAN MAKE THAT  CHARACTER TO THE MSB POSITION .. SO WE NEED TO FIND RANGE MAX QUERY FROM MSB  INDEX TO MSB + D INDEX , AFTER FIXING MSB POSITION WE CAN  MOVE TO NEXT  POSITION ... AND SO ON 

SEE THE CODE FOR CLARITY ..

-----------------------------------------CODE------------------------------------------------

#include<iostream>

#include<bits/stdc++.h>

using namespace std;

char arr[1010000];

int tree[6000000];

int has[1000001];

#define inf 999999999

int query(int node,int start,int end,int r1,int r2)

 {

    if(start>end || r1>end || r2<start) return -inf;

   if(r1<=start && r2>=end)

    {

     return tree[node];

    }

    else

    {

     int q1=query(2*node,start,(start+end)/2,r1,r2);

     int q2=query(2*node+1,((start+end)/2)+1,end,r1,r2);

     return max(q1,q2);

    }

 }

void build(int node , int start,int end)

 {

  if(start==end) tree[node]=arr[start];

  else if(start>end) return ;

  else

   {

    build(2*node,start,(start+end)/2);

    build(2*node+1,((start+end)/2)+1,end);

    tree[node]=max(tree[2*node],tree[2*node+1]);

    return ;

   }

   

 }

int main()

 {

   int n;

    scanf("%d",&n);

        while(n--)

         {

            memset(tree,0,sizeof tree);

         scanf("%s",arr);

         int len=strlen(arr);

         int op;

          scanf("%d",&op);

          int opp=op;

           build(1,0,len-1);

             for(int i=0;i<len;i++)

              {

              if(op==0)

               break;

               else

               {

                int val=query(1,0,len-1,i,i+op);

                if(val>arr[i])

                 {

                  op--;//  DELETE ITH CHARACTED  SO REMAINING OPERATION IS OP-1

                  arr[i]='#';// HASH THAT THIS CHARACTER IS DELETED 

  }

}

 }

  int c=0;

  int maxi=len-opp;

 // cout<<maxi<<endl;

 for(int i=0;i<len;i++)

   {

    if(c>=maxi) break;

   if(arr[i]!='#')// MEANS THIS CHARACTER IS DELETED 

   {

    printf("%c",arr[i]);

    c++;

}

   

} 

printf("\n");

}

  return 0;

 }