给定两个字符串集合 $A = \{a_1, a_2, \dots, a_n\}$ 和 $B = \{b_1, b_2, \dots, b_m\}$。定义一个包含 $n \cdot m$ 个元素、由 $a_i$ 和 $b_j$ 两两拼接而成的序列 $S$：

$$S = (a_1b_1, a_1b_2, \dots, a_1b_m, a_2b_1, a_2b_2, \dots, a_2b_m, \dots, a_nb_1, a_nb_2, \dots, a_nb_m)$$

现在将序列 $S$ 按字典序排序，记排序后的序列为 $C = (c_1, c_2, \dots, c_{n \cdot m})$。

我们想要了解序列 $C$，但它太大了。因此，我们向程序提出 $q$ 次查询，第 $i$ 次查询询问 $c_{k_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$ 行包含 $n$ 个不同的非空字符串 $a_1, a_2, \dots, a_n$。

集合 $A$ 中字符串的总长度不超过 $10^6$。

接下来的 $m$ 行包含 $m$ 个不同的非空字符串 $b_1, b_2, \dots, b_m$。

集合 $B$ 中字符串的总长度不超过 $10^6$。

所有字符串均由小写英文字母组成。

下一行包含一个整数 $q$ ($1 \le q \le 1000$)，表示查询次数。

在接下来的 $q$ 行中，第 $i$ 行包含一个整数 $k_i$ ($1 \le k_i \le n \cdot m$)，表示查询 $C$ 中的第 $k_i$ 个元素。

输出格式

输出 $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}$。如果存在多个正确的答案，你可以输出其中任意一个。

样例

输入 1

2 3
a
ab
a
aa
ba
2
3
4

输出 1

2 1
1 3