Data science: k-nearest neighbours

k-nearest neighbours labels a new point by asking its closest training points. Implement it for points on a plane.

What to build

A program that classifies query points with k-nearest neighbours.

Requirements

  • For each query, take the k training points closest to it by straight-line distance; among points at equal distance, earlier training points come first.
  • Predict the label that appears most often among those k points; on a tie, the alphabetically first of the tied labels.
  • Print X Y -> LABEL for each query, with X and Y exactly as given.

Input

Line 1: n and k. Then n lines X Y LABEL. Then a line with q, followed by q lines X Y.

Output

One line per query.

Constraints

1 ≤ k ≤ n ≤ 500; 1 ≤ q ≤ 100; labels are single words.

Example

Input:

6 3
1 1 red
2 1 red
1 2 red
6 6 blue
7 6 blue
6 7 blue
3
2 2
5 5
4 4

Output:

2 2 -> red
5 5 -> blue
4 4 -> red

Why it works

Points that are close in feature space tend to share a label, so a vote among the nearest k smooths out the odd mislabelled point while keeping the decision local.

Examples

Example 1 · Input
6 3
1 1 red
2 1 red
1 2 red
6 6 blue
7 6 blue
6 7 blue
3
2 2
5 5
4 4
Expected output
2 2 -> red
5 5 -> blue
4 4 -> red
Example 2 · Input
2 1
0 0 a
10 0 b
3
3 0
7 0
5 0
Expected output
3 0 -> a
7 0 -> b
5 0 -> a

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Squared distance (dx² + dy²) orders points the same way as distance and avoids square roots.

Hint 2

sorted() is stable: training points at the same distance keep their input order.

Hint 3

On a tie in the vote, take the alphabetically first of the tied labels.

Solution

Show one correct solution (try it yourself first)
n, k = map(int, input().split())
train = []
for _ in range(n):
    x, y, label = input().split()
    train.append((float(x), float(y), label))
q = int(input())
for _ in range(q):
    sx, sy = input().split()
    x, y = float(sx), float(sy)
    near = sorted(train, key=lambda p: (p[0] - x) ** 2 + (p[1] - y) ** 2)[:k]
    votes = {}
    for _, _, label in near:
        votes[label] = votes.get(label, 0) + 1
    best = min(votes, key=lambda lab: (-votes[lab], lab))
    print(f"{sx} {sy} -> {best}")

Lesson: Prediction basics →