beecrowd | 1396

There's an Exam from Cris Today!

By Wanderley Guimarães, IME-USP Brazil
Timelimit: 1

Teacher Cristina is very demanding. She is famous for being really evil - and she likes this fact. However, it seems that she overdid it this time. Before her exam, she demanded all students to form a line before entering the classroom. They did. But when they were about to enter the room, she yelled: "Hey, why are you not lined up in increasing lexicographic order of your names!!!???".

Some students got angry and talked to the teacher, saying this was an abuse. To not be intransigents, they said they would allow at most k swaps of adjacent people in the line. The teacher liked their idea, and decided to assign this problem as an extra in the exam.

You are given a sequence of names and an integer k. Find the (lexicographic) smallest sequence that can be obtained with at most k swaps of adjacent elements. Your task is to solve this problem for Cristina's students so they can enter the classroom and start the exam.

Input

The input consists of several instances. Each instance starts with a line containing two integers n and k (1 ≤ n ≤ 100 , 0 ≤ k ≤ n), indicating the number of names and the maximum allowed number of swaps, respectively. The next line contains a sequence of n names. Each name is composed by at most 20 characters from 'a' to 'z'.

The program must stop processing when n = k = 0.

Output

For each instance, print "Instancia c", where c is the instance number. In the next line, print the resulting sequence of names. After each name, your program must print a blank space, including after the last one (for example, in the output of the first test case below: wanderleybthadeubchegadob, where b represents a blank space. After each instance, print a empty line, including after the last one.

Sample Input Sample Output

3 0
wanderley thadeu chegado
3 1
wanderley thadeu chegado
3 2
wanderley thadeu chegado
3 3
wanderley thadeu chegado
0 0

Instancia 1
wanderley thadeu chegado


Instancia 2
thadeu wanderley chegado


Instancia 3
chegado wanderley thadeu


Instancia 4
chegado thadeu wanderley