Given a string S consisting of lower case English alphabets and an integer K.

You need to form a new string P that follows the following conditions:

• Length of P should be equal to K + length of string S.
• P should only be formed by using the prefixes of string S.
• P should be lexicographically smallest.

Task

Determine the string P that satisfies all the given conditions.

Example

Assumptions

• N = 3
• K = 4
• S = bca

Approach

• Prefixes of S are "b", "bc", "bca".
• String P will be "bbbbbbb" of length 7 (N + K i.e. 3 + 4).

Function Description

Complete the solve function provided in the editor. This function takes the following 3 parameters and returns the valid string:

• N: Represents the size of string S.
• K: Represents the given integer.
• S: Represents the given string.

Input Format

Note: This is the input format you must use to provide custom input (available above the Compile and Test button).

• The first line contains a single integer T denoting the number of test cases.
• For each test case:
  • The first line contains a single integer N denoting the size of string S.
  • The second line contains a single integer K denoting the number of new characters added in string S.
  • The third line contains the string S.

Output Format

For each test case in a separate line, output a string P that satisfies all the given conditions.

Constraints

Code snippets (also called starter code/boilerplate code) 

This question has code snippets for C, CPP, Java, and Python.