長さNの文字列Sに対する接尾辞配列SAを,以下の手順で得られるN以下の正整数の順列として定義する.
Sのi文字目からj文字目までの部分文字列をS[i..j]と表す.ただし添字は1-indexedである.
たとえば,S="mississippi"の接尾辞配列SAは,以下のようになる.
入力として,長さNの文字列に対する接尾辞配列SAが与えられる.
SAが得られるような文字列のうち,辞書式順序でK番目(1-indexed)のものを求めよ.
ただし,元の文字列は,アルファベット順に'a'から数えて高々A個の文字のみからなる.
入力は以下の形式に従う.与えられる数は全て整数である.
N A K SA_1 SA_2 ... SA_N
SAが得られるような辞書式順序でK番目の文字列を1行に出力せよ.
K番目の文字列が存在しない場合,"Impossible"と出力せよ.
3 4 2 2 1 3
bad
A=4の場合,SA={2,1,3}となる文字列は"bac","bad","cad","cbd"の4通り.
したがって,辞書式順序で2番目の"bad"が答えとなる.
18 26 10275802967 10 14 9 13 7 8 2 6 11 18 12 1 4 3 16 5 17 15
ritsumeicampdaytwo