K-th String

Time Limit : 2 sec, Memory Limit : 65536 KB

K-th String

Problem Statement

長さNの文字列Sに対する接尾辞配列SAを,以下の手順で得られるN以下の正整数の順列として定義する.
Si文字目からj文字目までの部分文字列をS[i..j]と表す.ただし添字は1-indexedである.

  1. 各接尾辞S[i..N] (i=1,2,...,N)を辞書式順序(昇順)で整列する.
  2. 整列した各接尾辞の開始位置iを順に並べる.

たとえば,S="mississippi"の接尾辞配列SAは,以下のようになる.



入力として,長さNの文字列に対する接尾辞配列SAが与えられる.
SAが得られるような文字列のうち,辞書式順序でK番目(1-indexed)のものを求めよ.
ただし,元の文字列は,アルファベット順に'a'から数えて高々A個の文字のみからなる.

Input

入力は以下の形式に従う.与えられる数は全て整数である.

N A K
SA_1
SA_2
...
SA_N

Constraints

  • 1≦N≦10^5
  • 1≦A≦26
  • 1≦K≦10^{18}
  • 1≦SA_i≦N
  • i \neq j ならば SA_i \neq SA_j

Output

SAが得られるような辞書式順序でK番目の文字列を1行に出力せよ.
K番目の文字列が存在しない場合,"Impossible"と出力せよ.

Sample Input 1

3 4 2
2
1
3

Output for the Sample Input 1

bad

A=4の場合,SA={2,1,3}となる文字列は"bac","bad","cad","cbd"の4通り.
したがって,辞書式順序で2番目の"bad"が答えとなる.

Sample Input 2

18 26 10275802967
10
14
9
13
7
8
2
6
11
18
12
1
4
3
16
5
17
15

Output for the Sample Input 2

ritsumeicampdaytwo

Source: Ritsumeikan University Competitive Programming Camp 2013, Day2 , Problem set from Osaka University teams, Shiga, Japan, 2013-03-12
Problem Setter:  komiya ,  lyoz