StrCartesian

두 문자열 집합 $A = \{a_1, a_2, \ldots, a_n\}$과 $B = \{b_1, b_2, \ldots, b_m\}$이 주어진다. $a_i$와 $b_j$를 이어 붙인 문자열 $n \cdot m$개로 이루어진 수열을 다음과 같이 정의한다.

$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)$

수열 $S$를 사전순으로 정렬하고, 정렬된 수열을 $C = (c_1, c_2, \ldots, c_{n \cdot m})$라 하자.

$C$ 전체는 너무 커서 출력할 수 없으므로 $q$개의 질의가 주어진다. $i$번째 질의는 $c_{k_i}$를 묻는다. 이 문자열도 너무 길어서 출력하기 어렵다. 답이 $c = a_f + b_s$이면, 프로그램은 $(f, s)$ 쌍만 출력하면 된다.

첫 줄에 정수 $n$과 $m$ ($1 \le n, m \le 5 \cdot 10^4$)이 주어진다. 이는 집합 $A$와 $B$의 크기이다. 다음 $n$개의 줄에는 서로 다른 빈 문자열이 아닌 문자열 $a_1, a_2, \ldots, a_n$이 주어진다. 집합 $A$에 속한 문자열의 총 길이는 $10^6$을 넘지 않는다. 다음 $m$개의 줄에는 서로 다른 빈 문자열이 아닌 문자열 $b_1, b_2, \ldots, b_m$이 주어진다. 집합 $B$에 속한 문자열의 총 길이는 $10^6$을 넘지 않는다. 모든 문자열은 영어 소문자로만 이루어진다. 다음 줄에는 질의의 개수 $q$ ($1 \le q \le 1000$)가 주어진다. 이어서 $q$개의 줄에 각각 정수 $k_i$ ($1 \le k_i \le n \cdot m$)가 주어진다.

$q$개의 줄을 출력한다. $i$번째 줄에는 두 정수 $f_i$와 $s_i$ ($1 \le f_i \le n$, $1 \le s_i \le m$)를 출력한다. 이는 $c_{k_i}$가 $a_{f_i} b_{s_i}$와 같다는 뜻이다. 정답이 여러 개이면 그중 아무거나 출력해도 된다.