분수 정렬

칠판에 서로 다른 정수 $n$개로 이루어진 수열이 두 개 적혀 있다. $A = [a_1, a_2, \ldots, a_n]$와 $B = [b_1, b_2, \ldots, b_n]$이다.

이 두 수열로 $a_i / b_j$ 꼴의 분수 $n^2$개를 만든다. 각 분수를 약분한 뒤 작은 순서대로 정렬한다.

정수 $q$와 정수 $c_1, c_2, \ldots, c_q$가 주어진다. 각 $j$에 대해 정렬된 분수 중 $c_j$번째 분수를 출력한다.

첫째 줄에 $n$과 $q$가 주어진다 ($1 \le n \le 10^5$, $1 \le q \le 10^5$, $q \le n^2$). 추가로 $n \cdot q \le 10^5$ 조건이 성립한다.

둘째 줄에 서로 다른 정수 $a_1, a_2, \ldots, a_n$이 주어진다 ($1 \le a_i \le 10^6$).

셋째 줄에 서로 다른 정수 $b_1, b_2, \ldots, b_n$이 주어진다 ($1 \le b_i \le 10^6$).

넷째 줄에 서로 다른 정수 $c_1, c_2, \ldots, c_q$가 주어진다 ($1 \le c_i \le n^2$).

$q$개의 줄을 출력한다. $j$번째 줄에는 정렬된 분수 중 $c_j$번째 분수를 출력한다. 분수 $p/q$는 p q 형식으로 출력하며, 반드시 기약분수여야 한다.

예시에서 분수는 처음에 다음과 같다.

$\left[ \frac{3}{2}, \frac{3}{3}, \frac{3}{4}, \frac{3}{5}, \frac{4}{2}, \frac{4}{3}, \frac{4}{4}, \frac{4}{5}, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \frac{1}{5}, \frac{2}{2}, \frac{2}{3}, \frac{2}{4}, \frac{2}{5} \right]$

약분하면 다음과 같다.

$\left[ \frac{3}{2}, \frac{1}{1}, \frac{3}{4}, \frac{3}{5}, \frac{2}{1}, \frac{4}{3}, \frac{1}{1}, \frac{4}{5}, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \frac{1}{5}, \frac{1}{1}, \frac{2}{3}, \frac{1}{2}, \frac{2}{5} \right]$

정렬하면 다음과 같다.

$\left[ \frac{1}{5}, \frac{1}{4}, \frac{1}{3}, \frac{2}{5}, \frac{1}{2}, \frac{1}{2}, \frac{3}{5}, \frac{2}{3}, \frac{3}{4}, \frac{4}{5}, \frac{1}{1}, \frac{1}{1}, \frac{1}{1}, \frac{4}{3}, \frac{3}{2}, \frac{2}{1} \right]$