The nearest towns

nearest neighbour points tree heap geodata classic

A weather service sends the forecast for the town nearest to the user, and when the town is unclear, for several nearest ones to choose from. There are tens of thousands of towns and thousands of queries a second. You are given a list of towns, points on the plane, and queries: a point and a number k. For each query print the k nearest towns by ordinary distance on the plane, from nearest to farthest. If distances are equal, the town with the smaller number comes first.

The second test is the 45,227 towns of the world with 10 thousand people or more from the GeoNames gazetteer as points (longitude, latitude) in thousandths of a degree. For the problem these are just points on a plane, without regard to the Earth being round.

Input

The first line holds the number of towns n (1 ≤ n ≤ 50,000), then come n lines with their coordinates x y; the towns are numbered from one in input order, and different towns may have the same coordinates. Then the number of queries q (1 ≤ q ≤ 10,000) and q lines x y k, where 1 ≤ k ≤ min(5, n). All coordinates are integers, |x|, |y| ≤ 10⁷.

Output

For each query, on a separate line, the numbers of the k nearest towns separated by spaces, from nearest to farthest.

Examples

Example 1

Input

Output

Limits

Time · Python: 8000 ms
Time · Go: 1500 ms
Memory: 256 MB
Judging: 6 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

Going through all towns for each query is 50 thousand times 10 thousand, half a billion distances. You need a structure that throws away distant pieces of the map at once. Think of a binary tree where each node divides the plane with a line into two halves.

2Hint 2

In a k-d tree the search goes like this: first go down into the half where the query lies, and go into the other only if it may contain someone closer than the k-th best found. How can this be checked with one number? And what happens if the query is far from all the towns, for example if all the towns are on one line and the query is off to the side?

3The idea

Build a k-d tree: a node is the median along the axis along which the points of the subtree are spread wider. For each node keep the rectangle in which its whole subtree lies. The search is a depth-first walk: keep a heap of the k best with the worst on top, and go into a subtree only if the distance from the query to its rectangle is no greater than to the worst of the k best. Look at the nearer child first: this way the best are found earlier and cut off more.

4Walkthrough

The tree. Sort the points of a subtree by the chosen axis; the median becomes the node, the halves its children. A node’s rectangle is the union of its point and its children’s rectangles. The depth of the tree is log₂ n, building is O(n log² n) with a sort at each level.

Pruning. The squared distance from the query to a rectangle: along each axis, how far the query is left of the left edge or right of the right edge (otherwise zero), and the sum of squares. Nobody in the subtree is closer than this. If the heap is full and this distance is strictly greater than the distance to the worst in the heap, skip the subtree. Equal ones are not skipped: there may be a town at the same distance with a smaller number.

Why a rectangle and not a line. Classic pruning compares the best only with the distance to the node’s dividing line. If the query is far from all the towns, and the towns lie on one line, as in the fifth test, the best town found is distant, and a band of that width touches almost all the dividing lines: the search walks the whole tree. The distance to the rectangle also takes into account how far off to the side the query is, and prunes correctly.

All distances are integer squares, up to 8·10¹⁴, with no roots and no floating point.

4+Solution

5Complexity

Building O(n log² n), memory O(n). A query visits about log n + k nodes on average on uniformly scattered points; a k-d tree has no worst-case guarantee, but with rectangles and splitting along the wider axis the tests of this problem pass quickly.

6Common mistakes

Going through all towns. Correct, but 50 thousand towns for 10 thousand queries will not fit in the time. This is the problem’s wrong solution.
Strict pruning. If a subtree is skipped at equal distances, a town at the same distance with a smaller number is lost: in the fourth test each grid node holds dozens of towns.
Axes in turn. If you split by x and y strictly in turn, for towns on one line half the splits fall on the axis where all the coordinates are equal: such a split divides nothing, and the search often goes into both halves.
Distances in double. Integer squares are enough for comparison; a root and floating point only add ties that are not there.

Algorithms behind it

GEO Data structure k-d tree A binary tree that splits space along the axes in turn: the nearest point in tens of steps instead of a full scan. O(n log n) to build; O(log n) per query on average 1 problem DS Data structure Binary heap The minimum at hand, insertion and extraction in O(log n): the tree in an array that event calendars live on. O(log n) 2 problems