In the royal bakery, the head chef decided to bake the most even pancake in the world. He baked a pancake in the shape of a strictly convex polygon $A$, whose vertices $A_1, A_2, \ldots, A_n$ were listed in counterclockwise order.

After that, the chef’s assistant decided to “make the shape a little neater”: on each side, he marked its midpoint, connected the marked points in order, and cut off all the dough outside the resulting polygon. The head chef didn’t even have time to object before the assistant repeated the same thing once again.

Formally, polygon $B$ was first obtained from polygon $A$:

$$B_i = \frac{A_i + A_{i+1}}{2},$$

and then polygon $C$ was obtained from polygon $B$ in the same way:

$$C_i = \frac{B_i + B_{i+1}}{2},$$

where $A_{n+1} = A_1$ and $B_{n+1} = B_1$.

Now only the final polygon $C$ is left on the table. The head chef is sure that the assistant ruined everything and demands that the pancake be restored to the shape it had before the cuttings. Meanwhile, the assistant has already been arguing for three hours about whether such a pancake could have been baked at all.

You need to restore any suitable initial polygon $A$, or report that no such polygon exists.

It is guaranteed that if an answer exists, then there exists a suitable polygon $A$ such that both coordinates of each of its vertices are integers, divisible by $4$, and do not exceed $10^9$ in absolute value.

Input

The first line contains a single integer $t$ ($1 \le t \le 7500$) — the number of test cases. The descriptions of the test cases follow.

The first line of each test case contains a single integer $n$ ($3 \le n \le 1000$) — the number of vertices of the polygon.

Each of the next $n$ lines contains two integers $x_i$ and $y_i$ ($|x_i|, |y_i| \le 10^9$) — the coordinates of point $C_i$.

It is guaranteed that, for each test case, the points $C_1, C_2, \ldots, C_n$ form a strictly convex polygon and are listed in counterclockwise order.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

Output

For each test case, print the answer.

If there is no suitable initial polygon, print NO.

Otherwise, print YES. Then print $n$ lines, the $i$-th of which should contain two coordinates of point $A_i$ separated by a space. The coordinates of the points may be real numbers whose absolute values do not exceed $4 \cdot 10^9$. The printed points must form a strictly convex polygon in counterclockwise order. In addition, for every $i$ the following inequality must hold:

$$[(A_{i+1} - A_i), (A_{i+2} - A_{i+1})] > 10^{-7},$$

where indices are taken modulo $n$, and

$$[V, U] = V_x U_y - V_y U_x.$$

Your answer is considered correct if, after applying the described operation twice to the polygon you printed, both coordinates of the $i$-th resulting point coincide with the coordinates of point $C_i$ with absolute or relative error at most $10^{-6}$.

You can print YES and NO in any case. For example, the strings yEs, yes, Yes, and YES will be recognized as positive answers.

Examples

Input 1

3
3
5 4
4 5
3 3
4
3 1
3 3
1 3
1 1
6
0 0
2 0
4 1
3 3
1 4
0 2

Output 1

YES
0 0
8 4
4 8
YES
0 0.5
4 -0.5
4 4.5
0 3.5
NO

Note

Illustration of the second test case: one of the possible polygons $A$ that generates the required polygon $C$: