题目描述

Fair King Tyrone and his four sons conquered the nation of Carrania. His four sons immediately started to squabble about dividing the land between the four of them. The main point of contention was the gold mines of Carrania - each son wanted to have no fewer gold mines than any other.

Fair King Tyrone soon got tired of the squabbling, especially when he learned the number of mines is $4N$, so dividing them should be easy. He gathered his sons, took a map, drew an X on it and declared each son would get one quarter of the nation, with borders defined by the X he drew.

Unfortunately, Fair King Tyrone is a bit shortsighted, and the map he drew on was not a map of Carrania. His first minister quickly hid the map, and now tries to draw an identical X on the map of Carrania so that each son gets the same number of gold mines. Unfortunately all sons saw King Tyrone draw the X, and know the borders should be two perpendicular straight lines - so the minister has to make them so.

Help him! Your task is to draw two perpendicular straight lines such that no gold mine lies on a border, and the borders divide the gold mines equally.

输入格式

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case begins with a number $N$, describing the number of gold mines each son should get. $4N$ lines follow, each containing two integers, being the coordinates $x_i$, $y_i$ of one of the gold mines. No three gold mines are co-linear.

输出格式

For each test case, output one line containing "Case #x: $x_a$ $y_a$ $x_b$ $y_b$", where $x$ is the case number (starting from 1), ($x_a$, $y_a$) are the coordinates of the point where the two borders intersect, and ($x_b$, $y_b$) are the coordinates of some other point on the X.

All coordinates must be between $-10^9$ and $10^9$, have at most 9 digits after the decimal point, and not use exponential notation. They must be exact: the resulting X will be drawn exactly at these coordinates. You should output IMPOSSIBLE instead if there is no good placement of borders.

2
1
0 0
1 0
0 1
1 1
1
1 0
0 1
-1 0
0 -1

Case #1: 0.5 0.5 2 0.5
Case #2: 0 0 -3 -3

提示

Limits

• $1 \leq T \leq 20$
• $-10^6 \leq x_i, y_i \leq 10^6$

Small dataset (10 Pts, Test set 1 - Visible)

• Time limit: 30 3 seconds.
• $1 \leq N \leq 10$

Large dataset (29 Pts, Test set 2 - Hidden)

• Time limit: 60 6 seconds.
• $1 \leq N \leq 2500$