王室のパン屋で、料理長は世界で最も均整の取れたパンケーキを焼くことにしました。彼は、頂点 $A_1, A_2, \ldots, A_n$ が反時計回りの順に並んだ狭義凸多角形 $A$ の形のパンケーキを焼きました。

その後、料理長の助手は「形を少し整える」ことにしました。各辺の中点に印を付け、印を付けた点を順に結び、できた多角形の外側にある生地をすべて切り落としました。料理長が異議を唱える間もなく、助手は同じことをもう一度繰り返しました。

形式的には、まず多角形 $A$ から多角形 $B$ を次のように得ました：

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

そして、同じ方法で多角形 $B$ から多角形 $C$ を得ました：

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

ここで、$A_{n+1} = A_1$、$B_{n+1} = B_1$ です。

今、台の上には最終的な多角形 $C$ だけが残っています。料理長は、助手がすべてを台無しにしたと確信し、パンケーキを切り落とす前の形に戻すよう要求しています。一方、助手は、そのようなパンケーキをそもそも焼くことができたのかについて、すでに3時間も議論しています。

条件を満たす元の多角形 $A$ をいずれか1つ復元するか、そのような多角形が存在しないことを報告してください。

解が存在するならば、各頂点の両座標が $4$ で割り切れる整数であり、絶対値が $10^9$ 以下であるような、条件を満たす多角形 $A$ が存在することが保証されます。

入力

最初の行には、テストケースの数を表す整数 $t$ ($1 \le t \le 7500$) が1つ与えられます。続いて各テストケースの説明が与えられます。

各テストケースの最初の行には、多角形の頂点数を表す整数 $n$ ($3 \le n \le 1000$) が1つ与えられます。

続く $n$ 行にはそれぞれ、点 $C_i$ の座標を表す2つの整数 $x_i$ と $y_i$ ($|x_i|, |y_i| \le 10^9$) が与えられます。

各テストケースにおいて、点 $C_1, C_2, \ldots, C_n$ は狭義凸多角形を形成し、反時計回りの順に並んでいることが保証されます。

すべてのテストケースにわたる $n$ の総和は $10^5$ 以下であることが保証されます。

出力

各テストケースについて、答えを出力してください。

条件を満たす元の多角形が存在しない場合は、NO を出力してください。

それ以外の場合は、YES を出力してください。その後、$n$ 行を出力してください。$i$ 行目には、点 $A_i$ の2つの座標を空白で区切って出力してください。点の座標は、絶対値が $4 \cdot 10^9$ 以下の実数でも構いません。出力した点は、反時計回りの順に狭義凸多角形を形成しなければなりません。さらに、すべての $i$ について次の不等式が成立しなければなりません：

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

ここで、添字は $n$ を法として扱い、

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

です。

出力した多角形に対して、説明した操作を2回適用した後、得られる $i$ 番目の点の両座標が点 $C_i$ の座標と絶対誤差または相対誤差 $10^{-6}$ 以下で一致する場合、答えは正しいとみなされます。

YES と NO は大文字と小文字を任意に組み合わせて出力できます。例えば、文字列 yEs、yes、Yes、YES はすべて肯定の答えとして認識されます。

入出力例

入力 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

出力 1

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

注記

2番目のテストケースの図：要求された多角形 $C$ を生成する、可能な多角形 $A$ の1つです：