시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB52125.000%

문제

На доске выписано две последовательности из $n$ различных целых чисел: $A = [a_1, a_2, \ldots, a_n]$ и $B = [b_1, b_2, \ldots, b_n]$.

Составим из них $n^2$ дробей вида $a_i / b_j$, сократим каждую дробь и отсортируем их по неубыванию.

Задано число $q$ и $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$.

На второй строке ввода находятся $n$ различных целых чисел $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^6$).

На третьей строке ввода находятся $n$ различных целых чисел $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le 10^6$).

На четвертой строке ввода находятся $q$ различных целых чисел $c_1, c_2, \ldots, c_q$ ($1 \le c_i \le n^2$).

출력

Выведите $q$ строк. На $j$-й строке выведите $c_j$-ю по неубыванию дробь среди получившихся. Дробь $p/q$ следует выводить в формате <<p q>>, дробь должна быть несократимой.

서브태스크

번호배점제한
114

$n \le 50$

213

$n \le 500$

315

$q \le 100$, $c_i \le 100$

421

$c_i \le 10^5$

537

예제 입력 1

4 8
3 4 1 2
2 3 4 5
1 16 2 4 5 6 10 15

예제 출력 1

1 5
2 1
1 4
2 5
1 2
1 2
4 5
3 2

힌트

В примере дроби исходно равны: $$\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].$$

채점 및 기타 정보

  • 예제는 채점하지 않는다.