You are given $N$ strings, namely $S_1, S_2, \ldots, S_N$.

$M$ other strings will be constructed as a concatenation of other strings. More specifically, the $i^\text{th} \ (N + 1 \leq i \leq N + M)$ string $S_i$ will be constructed as a concatenation of several other strings $S_k$, where $1 \leq k \leq i - 1$.

You must answer $Q$ queries consisting of an index $i \ (1 \leq i \leq N + M)$ and an integer $p \ (1 \leq p \leq \text{min}(|S_i|, 2^{50})$; you must print the $p^\text{th}$ character of $S_i$.

Input

The first line contains two integer $N$ and $M$.

The next $N + M$ lines describe $S_1, S_2, \ldots, S_{N+M}$.

The first $N$ lines consist of actual strings $S_1, S_2, ..., S_N$.

The next $M$ lines describe the construction of $S_{N+1}, S_{N+2}, \ldots, S_{N+M}$. Every line $i \ (1 \leq i \leq M)$ consists of an integer $k_i$ and $k_i$ indices $q_{i_1}, q_{i_2}, \ldots, q_{i_{k_i}}$, meaning that $S_{i+N} = S_{q_{i_1}} + S_{q_{i_2}} + \ldots + S_{q_{i_{k_i}}}$, where $+$ is the string concatenation operator.

The next line contains an integer $Q$.

Each of the following $Q$ lines consist of two integers $i$ and $p$.

Output

Print a string of $Q$ characters, in which the $i^\text{th}$ character represents the answer for the $i^\text{th}$ query.

Notes

• $1 \leq N, M, Q \leq 10^5$
• $1 \leq |S_i|$ for $1 \leq i \leq N + M$
• $\sum\limits_{i=1}^{N} |S_i| \leq 10^6$
• $\sum\limits_{i=1}^{M} k_i \leq 10^6$
• $1 \leq q_{i_t} \leq i + N - 1$ for $1 \leq i \leq M$ and $1 \leq t \leq k_i$
• All strings consist of lowercase English characters