33397번 - StrCartesian 스페셜 저지다국어

문제

Given are two sets of strings $A = \{a_1, a_2, \ldots, a_n\}$ and $B = \{b_1, b_2, \ldots, b_m\}$. Define a sequence of $n \cdot m$ pairwise concatenations of $a_i$ and $b_j$: $$S=(a_1 b_1, a_1 b_2, \ldots, a_1 b_m, a_2 b_1, a_2 b_2, \ldots, a_2 b_m, \ldots, a_n b_1, a_n b_2, \ldots, a_n b_m)\text{.}$$

Now sort the sequence $S$ lexicographically, and let the sorted sequence be $C = (c_1, c_2, \ldots, c_{n \cdot m})$.

We want to know the sequence $C,ドル but it is too large. So we make $q$ queries to your program, and the $i$-th query asks for $c_{k_i}$.

However, $c_{k_i}$ is still too long to output. If the answer equals $c = a_f + b_s,ドル then your program only needs to output the pair $(f, s)$.

입력

The first line contains two integers $n$ and $m$ (1ドル \le n, m \le 5 \cdot 10^4$), the sizes of sets $A$ and set $B$.

The following $n$ lines contain $n$ distinct non-empty strings $a_1, a_2, \ldots, a_n$.

The total length of strings in set $A$ does not exceed 10ドル^6$.

The following $m$ lines contain $m$ distinct non-empty strings $b_1, b_2, \ldots, b_m$.

The total length of strings in set $B$ does not exceed 10ドル^6$.

All strings consist of lowercase English letters.

The next line contains one integer $q$ (1ドル \le q \le 1000$), the number of queries.

In the following $q$ lines, the $i$-th line contains an integer $k_i$ (1ドル \le k_i \le n \cdot m$), specifying that the query asks for the $k_i$-th element of $C$.

출력

Print $q$ lines. The $i$-th line must contain two integers $f_i$ and $s_i$ (1ドル \le f_i \le n$; 1ドル \le s_i \le m$) specifying that the answer $c_{k_i}$ equals to $a_{f_i} b_{s_i}$. If there are multiple correct answers, your program may output any one of them.

제한

힌트