Background

Translated from ROIR 2022 D2T2.

Problem Description

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.

Input Format

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 Format

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.

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

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

Hint

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