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