Problem L
Lazy Learner

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.

Note

• 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$.

Input

• 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.

Output

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.

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