Kth Good Substring

Problem Statement

英小文字からなる文字列 $S$ , 英小文字全体からなる集合の部分集合 $T = \{ T_1, T_2, \ldots, T_N \}$ , 正整数 $K$ が与えられます。ただし、 $N = 0$ のときは $T = \{\}$ です。

$S$の良い部分文字列を$S$ の部分文字列であって、 $T$ に属する文字をひとつも含まないものと定義します。

$S$ の良い部分文字列の中で、辞書順で $K$ 番目に小さいものを出力してください。良い部分文字列が $K$ 個未満の場合は -1 を出力してください。

この問題においては、文字列として等しい部分文字列は取り出す位置が異なっても区別しません。

Constraints

• $1 \leq |S| \leq 200{,}000$
• $1 \leq K \leq 2 \times 10^{10}$
• $0 \leq N \leq 26$
• $T_i$ は英小文字
• $T$ の要素は互いに相異なる

Input

$S$ $K$
$N$
$T_1$ $T_2$ $\ldots$ $T_N$

$N = 0$ のとき、入力に$3$行目が存在しないことに注意してください。

Output

$S$ の良い部分文字列の中で、辞書順で $K$ 番目に小さいものを出力してください。良い部分文字列が $K$ 個未満の場合は -1 を出力してください。

Sample

Sample Input 1

aaa 2
0

Sample Output 1

aa

Sample Input 2

mississippi 5
1
i

Sample Output 2

ss

Sample Input 3

abracadabra 8
2
b d

Sample Output 3

rac

Sample Input 4

aizucompetitiveprogrammingcamp 16
2
m o

Sample Output 4

etitive

---