NNS - Nearest Neighbor Search

no tags 

You are given N (N <= 100 000) d-dimensional (1 <= d <= 5) points, each having integer coordinates (X1, X2, ..., Xd). Then Q (Q <= 100 000) queries follow. For each query you are given a d-dimensional point (not necessarily from the given N) and you are to find the squared Euclidean distance to the closest point from the given N.

The coordinates of all N+Q points are generated randomly between -1 000 000 000 and 1 000 000 000.

The squred Euclidean distance between two points A and B is the sum of (A.Xi-B.Xi)*(A.Xi-B.Xi) for i=1, 2, ..., d.

Input

The first line contains three numbers - N, d and Q.

The next N lines contain d integers each - the coordinates of a point.

The next Q lines contain d integers each - the coordinates of a query point.

Output

Print the answer for each of the Q queries on separate lines.

Example

Input:
2 2 2
2 2 2 1 1 2 2 1 1 3 3
1 1
2 2
3 3
Output:
0
2

hide comments
visleck: 2017-08-29 11:33:25

@extazy: Constraints on d??

RE: I am really sorry, I must have deleted it while adjusting the constraints on N and Q. It is up to 5.

Last edit: 2017-08-29 20:51:47

Added by:Extazy
Date:2017-08-29
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All