Inverse Rotational Compression

Given a transformed string (S') of length (n) and an integer (p) (1-indexed), recover the original string (S). The transformation is defined as follows:

1. For an original string (S) of length (n), generate (n) strings. The (i)-th string is obtained by moving the first (i-1) characters of (S) to its end.

2. Sort these (n) strings by their first character in increasing order. If two strings have the same first character, they are ordered by their original position in (S) (i.e. smaller index comes first).

3. Form (S') by concatenating the last character of each sorted string in order. Note that (S') is a permutation of (S). Additionally, let (p) be the position (in the sorted order) where the original string (S) appears.

Your task is to invert this transformation. Given (S') and (p), recover and output the original string (S).

The inverse transformation is analogous to the inverse Burrows–Wheeler Transform. Use the following approach:

• Let (L = S') and let (F) be the sorted version of (L).
  
• Compute the next array which maps each occurrence of a letter in (L) to its corresponding occurrence in (F).
  
• Start from index (p-1) in (L) and reconstruct (S) by following the next pointers for (n) iterations.
  
  It is guaranteed that (S) consists only of lowercase letters.

inputFormat

Input consists of two lines. The first line contains the transformed string (S') (a non-empty string of lowercase letters). The second line contains an integer (p) representing the 1-indexed position of the original string in the sorted rotations.

outputFormat

Output the recovered original string (S).

sample

xelpame
7

example