[Solution] Not a Cheap String Codeforces Solution

D. Not a Cheap String

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Let s$s$ be a string of lowercase Latin letters. Its price is the sum of the indices of letters (an integer between 1 and 26) that are included in it. For example, the price of the string abca is 1+2+3+1=7$1+2+3+1=7$.

The string w$w$ and the integer p$p$ are given. Remove the minimal number of letters from w$w$ so that its price becomes less than or equal to p$p$ and print the resulting string. Note that the resulting string may be empty. You can delete arbitrary letters, they do not have to go in a row. If the price of a given string w$w$ is less than or equal to p$p$, then nothing needs to be deleted and w$w$ must be output.

Note that when you delete a letter from w$w$, the order of the remaining letters is preserved. For example, if

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

 you delete the letter e from the string test, you get tst.

Input

The first line of input contains an integer t$t$ (1≤t≤104$1\le t\le {10}^4$) — the number of test cases in the test. The following are descriptions of t$t$ test cases.

Each case consists of two lines.

Round Down the Price Codeforces Solution

Polycarp Writes a String from Memory Codeforces Solution

Train and Queries Codeforces Solution

Not a Cheap String Codeforces Solution

Split Into Two Sets Codeforces Solution

Equate Multisets Codeforces Solution

Passable Paths (easy version) Codeforces Solution

Passable Paths (hard version) Codeforces Solution

The first of them is the string w$w$, it is non-empty and consists of lowercase Latin letters. Its length does not exceed 2⋅105$2\cdot {10}^5$.

The second line contains an integer p$p$ (1≤p≤5200000$1\le p\le 5200000$).

It is guaranteed that the sum of string lengths w$w$ over all test cases does not exceed 2⋅105$2\cdot {10}^5$.

Output

Output exactly t$t$ rows, the i$i$-th of them should contain the answer to the i$i$-th set of input data. Print the longest string that is obtained from w$w$ by deleting letters such that its price is less or equal to p$p$. If there are several answers, then output any of them.

Note that the empty string  — is one of the possible answers. In this case, just output an empty string.