Build a classifier that does no training at all. The hard part is not the distance calculation — it is how you break ties, which is where implementations diverge.

Input

X_train  # (n, d) real-valued features
y_train  # (n,)  integer labels
X_query  # (m, d) points to predict
k        # neighbor count (at least 1)

If X_train or X_query arrives one-dimensional, treat it as (n, 1) / (m, 1).

Distance

Use Euclidean distance, square root included.

$d(a, b) = \sqrt{\sum_i (a_i - b_i)^2}$

Neighbors and voting — the tie rules

Ties decide the answer, so follow these exactly.

• Sort candidates by (distance, training index) ascending and take the first k. On equal distance the lower index comes first.
• Take a majority vote over those k labels. On a tie, pick the smaller label value.
• If k exceeds the number of training samples, use all of them.

Return

knn_predict(X_train, y_train, X_query, k) → a list of m labels.

Implement knn_predict(X_train, y_train, X_query, k).

• Use Euclidean distance (square root included).
• Neighbors are the first k by (distance, index) ascending.
• On a voting tie, pick the smaller label value.
• If k exceeds the training set size, use all of it.
• Return a list of m labels.