問題文
1 から N までの番号がついた,N 個の文字列 S(1),S(2),…,S(N) があります.
MojaMoja君は,これら N 個の文字列から M 個を選び,それらの頭文字を順に繋ぎ合わせて,長さ M の文字列 H を作りました.
文字列を選ぶ際には同じものを何度でも選んでよかったものとします.
この H を作ることのできる,M 個の文字列 T(1),T(2),…,T(M) の選び方としてあり得るもののうちで,辞書順で K 番目に小さいものは何でしょうか?
すなわち,N 個の文字列 S(1),S(2),…,S(N) から重複を許して M 個を選び,それらを選んだ順に T(1),T(2),…,T(M) とするとき,文字列の列 T=(T(1),T(2),…,T(M)) であって,次に示す条件を満たすようなもののうちで,辞書順で K 番目に小さいものを求めてください.
条件
- 先頭から順に,各文字列の先頭の文字を連結して得られる,長さ M の文字列 T1(1)T1(2)…T1(M) が H と等しい
T1(i)(1≤i≤M) は,文字列 T(i) の先頭の文字を表します.
ここで,条件を満たすような T としてあり得る文字列の列が,必ず K 個以上存在することが保証されます。
なお,ある長さ l の文字列の列 X1,X2,…,Xl が,ある長さ l の文字列の列 Y1,Y2,…,Yl より辞書順で小さいとは,ある整数 i(1≤i≤l) が存在して,列 X と列 Y とは先頭の i−1 項が一致しており,かつ, 文字列 Xi が文字列 Yi よりも辞書順で真に小さいことを指します.
制約
- 1≤N,M≤2×105
- 1≤K≤1018
- ∣H∣=M
- 1≤∣S(i)∣≤100(1≤i≤N)
- i=j ならば S(i)=S(j)(1≤i,j≤N)
- N,M,K は整数である
- H,S(i)(1≤i≤N) は半角英小文字のみからなる
- 本文中の条件を満たす T としてあり得る列は K 個以上存在する
- 答えとなる文字列の列を (V(1),V(2),…,V(M)) として 1≤i≤M∑∣V(i)∣≤106
入力
入力は以下の形式で標準入力から与えられる.
出力
答えとなる列を,空白もしくは改行区切りで出力せよ.
サンプル
入力例1
6 3 6
tgc
competition
the
grand
contest
gray
topcoder
出力例1
topcoder grand contest
問題文中の条件を満たすような列 T は,辞書順で昇順に
(“the”,“grand”,“competition”),(“the”,“grand”,“contest”),(“the”,“gray”,“competition”),(“the”,“gray”,“contest”),(“topcoder”,“grand”,“competition”),(“topcoder”,“grand”,“contest”),(“topcoder”,“gray”,“competition”),(“topcoder”,“gray”,“contest”)
の 8 つです.