# Palace

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)

### Problem Description

The last trial Venus imposes on Psyche is a quest to the underworld. She is to take a box and obtain in it a dose of the beauty of Prosperina, queen of the underworld.
There are $n$ palaces in the underworld, which can be located on a 2-Dimension plane with $(x, y)$ coordinates (where $x, y$ are integers). Psyche would like to find the distance of the closest pair of two palaces. It is the password to enter the main palace.
However, the underworld is mysterious and changes all the time. At different times, exactly one of the $n$ palaces disappears.
Psyche wonders what the distance of the closest pair of two palaces is after some palace has disappeared.
Print the sum of the distance after every single palace has disappeared.
To avoid floating point error, define the distance $d$ between palace $(x_1, y_1)$ and $(x_2, y_2)$ as $d = (x_1 - x_2) ^ 2 + (y_1 - y_2) ^ 2$.

### Input

The first line of the input contains an integer $T$ $(1 \le T \le 5)$, which denotes the number of testcases.
For each testcase, the first line contains an integers $n$ $(3 \le n \le 10 ^ 5)$, which denotes the number of temples in this testcase.
The following $n$ lines contains $n$ pairs of integers, the $i$-th pair $(x, y)$ $(-10 ^ 5 \le x,y \le 10 ^ 5)$ denotes the position of the $i$-th palace.

### Output

For each testcase, print an integer which denotes the sum of the distance after every single palace has disappeared.

1
3
0 0
1 1
2 2

### Sample Output

12

Hint

If palace $(0,0)$ disappears，$d = (1-2) ^ 2 + (1 - 2) ^ 2 = 2$; If palace $(1,1)$ disappears，$d = (0-2) ^ 2 + (0 - 2) ^ 2 = 8$; If palace $(2,2)$ disappears，$d = (0-1) ^ 2 + (0-1) ^ 2 = 2$; Thus the answer is $2 + 8 + 2 = 12$。

KD-tree

CDQ分治

# Finding Hotels

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 102400/102400 K (Java/Others)

### Problem Description

There are N hotels all over the world. Each hotel has a location and a price. M guests want to find a hotel with an acceptable price and a minimum distance from their locations. The distances are measured in Euclidean metric.

### Input

The first line is the number of test cases. For each test case, the first line contains two integers N (N ≤ 200000) and M (M ≤ 20000). Each of the following N lines describes a hotel with 3 integers x (1 ≤ x ≤ N), y (1 ≤ y ≤ N) and c (1 ≤ c ≤ N), in which x and y are the coordinates of the hotel, c is its price. It is guaranteed that each of the N hotels has distinct x, distinct y, and distinct c. Then each of the following M lines describes the query of a guest with 3 integers x (1 ≤ x ≤ N), y (1 ≤ y ≤ N) and c (1 ≤ c ≤ N), in which x and y are the coordinates of the guest, c is the maximum acceptable price of the guest.

### Output

For each guests query, output the hotel that the price is acceptable and is nearest to the guests location. If there are multiple hotels with acceptable prices and minimum distances, output the first one.

2
3 3
1 1 1
3 2 3
2 3 2
2 2 1
2 2 2
2 2 3
5 5
1 4 4
2 1 2
4 5 3
5 2 1
3 3 5
3 3 1
3 3 2
3 3 3
3 3 4
3 3 5

1 1 1
2 3 2
3 2 3
5 2 1
2 1 2
2 1 2
1 4 4
3 3 5