Description

You are given integer arrays $a, b, p, q$ of length $n$, and define the function $f(i,j)=\dfrac{a_i+b_j}{p_i+q_j}(1\le i,j\le n)$.

You are also given two integers $x, y$. You need to find a pair $(i,j)$ such that $f(i,j)$ is the $x$-th smallest among all $f(i,t)(t=1,2,\cdots,n)$, and is the $y$-th smallest among all $f(s,j)(s=1,2,\cdots,n)$.

In this problem, we say that a number $x$ is the $k$-th smallest in a sequence $c_{1\ldots n}$ if and only if in $c$ there are exactly $\alpha$ numbers $y$ satisfying $y<x$, and exactly $\beta$ numbers $y$ satisfying $y\le x$, and at the same time $\alpha<k\le \beta$.

If no such $(i,j)$ exists, output 0 0.

If there are multiple such $(i,j)$, output any one of them.

Since balance issues cannot be clarified in a single question, the problem setter will ask you multiple times.

Input Format

This problem contains multiple test cases.

The first line contains an integer $T$ indicating the number of test cases. For each test case:

The first line contains three positive integers $n, x, y$.

In the next $n$ lines, each line contains $4$ integers. The $i$-th line contains four integers $a_i, b_i, p_i, q_i$.

Output Format

Output $T$ lines. Each line contains two integers, representing the $(i,j)$ you found.

1
3 3 2
2 4 1 4
10 4 3 4
1 3 1 3

1 3

Hint

[Sample Explanation #1]

• $f(1,1)=1.2;f(1,2)=1.2;f(1,3)=1.25$.
• $f(2,1)=2;f(2,2)=2;f(2,3)=2\frac{1}{6}$.
• $f(3,1)=1;f(3,2)=1;f(3,3)=1$.

$f(1,3)$ is the $3$-rd smallest among $f(1,1), f(1,2), f(1,3)$, and $f(1,3)$ is the $2$-nd smallest among $f(1,3), f(2,3), f(3,3)$.

[Constraints]

This problem uses bundled testdata.

For $100\%$ of the data, $1 \le x,y \le n \le 5 \times 10^5$, $\sum n \le 5 \times 10^5$, $|a_i|,|b_i|\le 10^9$, $0<p_i,q_i\le 10^9$, where $\sum n$ denotes the sum of $n$ over all test cases.

[Tips and Help]

The input size of this problem is large, so please choose a faster input method.

Translated by ChatGPT 5