Alphabetically smallest word P84412


Statement
 

pdf   zip

html

Given a string s made up of only lowercase letters, and a natural number k, remove any substring of length k from s so that the result is the lexicographically smallest possible word.

Input

Input consists of several cases, each with s and k. Assume 1 ≤ k < | s | ≤ 104.

Output

For every case, print the alphabetically smallest word that can be obtained after removing k consecutive letters from s.

Public test cases
  • Input

    abba 1
    abba 2
    abba 3
    zxazyzy 3
    

    Output

    aba
    aa
    a
    zxay
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Tretzè Concurs de Programació de la UPC - Semifinal
    Date
    2015-07-01