Lang is very lazy at learning English. He is always getting distracted during English classes. Being happy with the sweet message he got from his girlfriend yesterday, Lang invented a game to play during his English class.
Lang has an English dictionary containing $n$ words, denoted as $T_1, T_2, \ldots , T_ n$. Denoting as $S$ the message he received, his game is as below:
First, he chooses two indices $\ell $ and $r$ $(1 \leq \ell \leq r \leq |S|)$.
Then, he considers the substring of $S$ from $\ell $ to $r$, he finds all words in his dictionary which are subsequences of this substring.
Next, he sorts all these words in lexicographic order.
Finally, he chooses a positive integer $k$ and wonders which is the $k$-th word of this list.
Lang wants to play this game $q$ times. However, he worries that the class would end before he finishes playing, so he asks you to write a program to find the $k$-th word quickly.
Given a string $S = s_1 s_2 \ldots s_ n$:
The substring of $S$ from $\ell $ to $r$ $(1 \leq \ell \leq r \leq n)$ is the string $s_\ell s_{\ell +1} \ldots s_ r$.
A string $T = t_1 t_2 \ldots t_ m$ is a subsequence of $S$ iff there exists a sequence of indices $1 \leq i_1 < i_2 < \cdots < i_ m \leq n$ such that $S_{i_ j} = T_ j~ \forall 1 \leq j \leq m$.
A string $S = s_1 s_2 \ldots s_ n$ is lexicographically smaller than a string $T = t_1 t_2 \ldots t_ m$ iff any of the following is satisfied:
$n < m$ and $S_ i = T_ i~ \forall 1 \leq i \leq n$.
There exists an index $j$ such that $1 \leq j \leq \min (m,n), S_ i = T_ i~ \forall 1\leq i < j$ and $S_ j < T_ j$.
The first line contains a string $S$ of at most $500$ lowercase English characters — the message Lang received yesterday.
The second line contains two integers $n$ $(1 \leq n \leq 2 \cdot 10^4)$ — the number of words in Lang’s dictionary, and $q$ $(1 \leq q \leq 3 \cdot 10^5)$ — the number of times Lang plays his game.
Each of the next $n$ lines contain a non-empty string of lowercase English characters — a word in Lang’s dictionary. The total length of these $n$ words does not exceed $8 \cdot 10^4$.
Each of the last $q$ lines contain three positive integers $\ell $, $r$, and $k$ $(1 \leq \ell \leq r \leq |S|, 1 \leq k \leq n)$ presenting a game as described above.
Print $q$ lines describing the words Lang is looking for in these $q$ games. If the length of the word is longer than $10$ characters, print only the first $10$ characters. If in some game, that word does not exist (i.e, $k$ is greater than the number of words in the list), print ‘NO SUCH WORD’ instead.
Please note that the checker of this problem is case-sensitive.
Sample Input 1 | Sample Output 1 |
---|---|
abcd 3 5 a ac bd 1 3 1 1 3 2 1 3 3 2 4 1 2 4 2 |
a ac NO SUCH WORD bd NO SUCH WORD |