n<=1e5, q<=n^2, k<=n^2, qn<=1e5

a and b are integer arrays of length n. q queries are asked and you need to find k-th largest fraction among ai/bj (0<=i,j<n). You can do it offline.

(Note: binary searching on ai/bj as a float/double/long double does not work due to precision. I could not find any judge to submit the solution sorry.)

Edit: you need to output the nominator and denominator as the solution for each query.

Edit: ai,bi<=1e6

Edit: Apparently solutions binary searching float/double/long double work. Sorry for confusion.