J. Running in the Plane
time limit per test
1 second
memory limit per test
1024 mebibytes
input
standard input
output
standard output

You are given a set $$$S = \{(a_1, b_1), (a_2, b_2), \dots, (a_n, b_n)\}$$$ of $$$n$$$ points in the plane. All coordinates of $$$S$$$ are integers.

A set $$$T = \{(c_1, d_1), (c_2, d_2), \dots, (c_m, d_m)\}$$$ of $$$m$$$ 2-dimensional vectors is called a good set of $$$S$$$ if it satisfies the following:

  1. There exists a nonempty finite sequence $$$((x_0, y_0), (x_1, y_1), \dots, (x_l, y_l))$$$ of points in the plane such that
    1. $$$(x_0, y_0) = (0, 0)$$$.
    2. For all points $$$p$$$ in $$$S$$$, there exists an integer $$$i$$$ ($$$0 \le i \le l$$$) such that $$$(x_i, y_i) = p$$$.
    3. For all integers $$$i$$$ ($$$0 \le i \lt l$$$), the vector $$$(x_{i+1} - x_i, y_{i+1} - y_i)$$$ is in $$$T$$$.
  2. For all integers $$$i$$$ ($$$1 \le i \le m$$$), two numbers $$$c_i$$$ and $$$d_i$$$ are integers between $$$-10^{18}$$$ and $$$10^{18}$$$ inclusive.

Find any good set of minimum size.

Input

The input consists of multiple test cases. The first line contains an integer $$$Q$$$ — the number of test cases. The description of the test cases follows. For each test case:

  • The first line of the test case contains an integer $$$n$$$ — the number of points in $$$S$$$.
  • The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$a_i$$$ and $$$b_i$$$ — the coordinates of each point in $$$S$$$.
Output

For each test case:

  • Let $$$T = \{(c_1, d_1), (c_2, d_2), \dots, (c_m, d_m)\}$$$ be a minimum-size good set of $$$S$$$.
  • In the first line of the test case, print an integer $$$m$$$ — the number of vectors in $$$T$$$.
  • In the $$$i$$$-th of the next $$$m$$$ lines, print two integers $$$c_i$$$ and $$$d_i$$$ — the coordinates of each vector.

If there are multiple solutions, print any of them.

It can be proved that, under the constraints of this problem, a good set of $$$S$$$ with size at most $$$10 \times n$$$ always exists.

Scoring
  • $$$1 \le Q \le 50\,000$$$
  • The sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.
  • $$$2 \le n \le 10^5$$$
  • $$$-10^8 \le a_i, b_i \le 10^8$$$ ($$$1 \le i \le n$$$)
  • $$$(a_i, b_i) \ne (a_j, b_j)$$$ ($$$1 \le i \lt j \le n$$$)
  • $$$m \ge 0$$$
  • $$$-10^{18} \le c_i, d_i \le 10^{18}$$$ ($$$1 \le i \le m$$$)
  • $$$(c_i, d_i) \ne (c_j, d_j)$$$ ($$$1 \le i \lt j \le m$$$)
Example
Input
2
2
-30 30
-50 50
3
2 1
1 0
4 1
Output
1
-10 10
2
1 0
1 1
Note

In the first test case, $$$T = \{(-10,10)\}$$$ is a minimum-size good set of $$$S = \{(-30,30), (-50,50)\}$$$.

We can take a sequence $$$((0,0), (-10,10), (-20,20), \underline{(-30,30)}, (-40,40), \underline{(-50,50)})$$$. Here, the underlined points are in $$$S$$$.

In the second test case, $$$T = \{(1,0), (1,1)\}$$$ is a minimum-size good set of $$$S = \{(2,1), (1,0), (4,1)\}$$$.

We can take a sequence $$$((0,0), \underline{(1,0)}, \underline{(2,1)}, (3,1), \underline{(4,1)})$$$.