왕실 제과점의 수석 요리사는 세상에서 가장 고른 팬케이크를 만들기로 했다. 그는 엄밀한 볼록 다각형 $A$ 모양의 팬케이크를 구웠으며, 꼭짓점 $A_1,A_2,\ldots,A_n$은 반시계 방향 순서로 나열되어 있었다.

그 후 요리사의 조수는 “모양을 조금 더 깔끔하게” 만들기로 했다. 각 변의 중점을 표시하고, 표시한 점들을 순서대로 연결한 뒤, 만들어진 다각형 바깥의 반죽을 모두 잘라냈다. 수석 요리사가 미처 반대하기도 전에 조수는 같은 작업을 한 번 더 반복했다.

정확히 말하면, 먼저 다각형 $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$만 남아 있다. 수석 요리사는 조수가 모든 것을 망쳤다고 확신하며 팬케이크를 자르기 전 모양으로 복원하라고 요구한다. 한편 조수는 애초에 그런 팬케이크를 구울 수 있었는지를 놓고 벌써 세 시간째 논쟁하고 있다.

조건에 맞는 초기 다각형 $A$를 아무거나 복원하거나, 그런 다각형이 존재하지 않음을 알려야 한다.

답이 존재한다면, 각 꼭짓점의 두 좌표가 모두 $4$로 나누어떨어지는 정수이고 절댓값이 $10^9$ 이하인 적절한 다각형 $A$가 존재함이 보장된다.

입력

첫 번째 줄에 테스트 케이스의 개수인 정수 $t$ ($1\le t\le7500$)가 주어진다. 이어서 각 테스트 케이스의 설명이 주어진다.

각 테스트 케이스의 첫 번째 줄에 다각형의 꼭짓점 개수인 정수 $n$ ($3\le n\le1000$)이 주어진다.

다음 $n$개의 줄 각각에 점 $C_i$의 좌표인 두 정수 $x_i$, $y_i$ ($|x_i|,|y_i|\le10^9$)가 주어진다. 각 테스트 케이스에서 점 $C_1,C_2,\ldots,C_n$은 엄밀한 볼록 다각형을 이루며 반시계 방향 순서로 나열됨이 보장된다.

모든 테스트 케이스에 걸친 $n$의 합은 $10^5$ 이하임이 보장된다.

출력

각 테스트 케이스마다 답을 출력한다.

적절한 초기 다각형이 없다면 NO를 출력한다.

그렇지 않다면 YES를 출력한다. 그다음 $n$개의 줄을 출력하며, $i$번째 줄에는 점 $A_i$의 두 좌표를 공백으로 구분하여 출력해야 한다. 점의 좌표는 절댓값이 $4\cdot10^9$ 이하인 실수여도 된다. 출력한 점들은 반시계 방향 순서로 엄밀한 볼록 다각형을 이루어야 한다. 또한 모든 $i$에 대해 다음 부등식이 성립해야 한다.

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

여기서 인덱스는 $n$을 법으로 하며,

$$[V,U]=V_xU_y-V_yU_x.$$

출력한 다각형에 위에서 설명한 연산을 두 번 적용했을 때, 그 결과의 $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

참고

두 번째 테스트 케이스의 그림이다. 요구되는 다각형 $C$를 만들어내는 가능한 다각형 $A$ 중 하나를 나타낸다.