P10091 [ROIR 2022] Fraction Sorting (Day 2).

Translated from [ROIR 2022 D2T2](https://neerc.ifmo.ru/school/archive/2021-2022/ru-olymp-regional-2022-day2.pdf).

There are two sequences $A = [a_1, a_2, \dots , a_n]$ and $B = [b_1, b_2, \dots , b_n]$, each consisting of $n$ distinct integers. Combine them into $n^2$ fractions of the form $\frac{a_i}{b_j}$, reduce each fraction to simplest form, and then sort them in increasing order. You are given a number $q$ and $q$ integers $c_1, c_2, \dots , c_q$. For each $c_i$, output the $c_i$-th smallest fraction among the $n^2$ fractions described above.

The first line contains two integers $n$ and $q$. The second line contains $n$ distinct integers $a_1, a_2, \dots, a_n$. The third line contains $n$ distinct integers $b_1, b_2, \dots, b_n$. The fourth line contains $q$ distinct integers $c_1, c_2, \dots, c_q$.

Output $q$ lines. The $i$-th line should output the $c_i$-th fraction in the increasing order. A fraction $\frac{p}{q}$ should be printed in the format `p q`, and it must be in simplest form.

In the sample, the initial list of fractions is: $$ \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], $$ After reducing, we get: $$ \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], $$ Finally, after sorting in increasing order, we get: $$ \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]. $$ This problem uses bundled testdata. | Subtask | Score | Special Properties | | :----------: | :----------: | :----------: | | $1$ | $14$ | $n\le50$ | | $2$ | $13$ | $n\le500$ | | $3$ | $15$ | $q,c_i\le100$ | | $4$ | $21$ | $c_i\le10^5$ | | $5$ | $37$ | | For $100\%$ of the testdata, $1 \leq n \leq 10^5$, $1 \leq q \leq 10^5$, and $q \leq n^2, n \times q \leq 10^5$ (so in fact $q \le 1000\sqrt[3]{10}\approx2154$), $1 \leq a_i, b_i \leq 10^6$, $1 \leq c_i \leq n^2$. Translated by ChatGPT 5