Problem Visual

Problem Statement

You are given $N$ pairs of integers $(X_i, Y_i)~(i=1, 2, \dots, N)$.

For each of $i=1,2, \dots, N$, answer the following question.

• Does there exist a pair of integers $(A, B)$ satisfying the following conditions? If one exists, find $1$ such pair of integers $(A, B)$.
  • $-2 \times 10^9 \leq A \leq 2 \times 10^9$.
  • $-2 \times 10^9 \leq B \leq 2 \times 10^9$.
  • For every integer $j$ such that $1 \leq j \leq N, j \neq i$, it holds that $A X_j + B Y_j < A X_i + B Y_i$.

Constraints

• $1 \leq T \leq 10^5$
• Constraints for each test case
  • $2 \leq N \leq 2 \times 10^5$.
  • $-10^9 \leq X_i \leq 10^9, -10^9 \leq Y_i \leq 10^9 \quad (1 \leq i \leq N)$.
  • $i \neq j \Rightarrow (X_i, Y_i) \neq (X_j, Y_j) \quad (1 \leq i \leq N, 1 \leq j \leq N)$.
• Constraints for the entire test file
  • The sum of $N$ over the $T$ test cases is at most $2 \times 10^5$.
  • All input values are integers.

Input

$T$
${\rm Testcase}_1$
$\vdots$
${\rm Testcase}_T$

Each test case is given in the following format.

$N$
$X_1$ $Y_1$
$\vdots$
$X_N$ $Y_N$

Output

In order starting from test case $1$, output in the following format.

• Output $N$ lines. On the $k~(1 \leq k \leq N)$-th line, for the case $i=k$, if no pair of integers $(A, B)$ satisfying the conditions exists, output No; if one exists, output one example of such a pair of integers, in the order $A, B$, separated by a space.

Sample

2
5
1 0
0 -2
-3 0
0 4
0 0
9
0 0
1 1
2 2
3 3
4 4
5 3
6 2
7 1
8 0

10 -1
-5 -9
-5 2
2 2
No
-1 0
No
No
No
0 1
No
No
No
1 0