Given training points Xtr (n, d) with integer labels ytr (n,), queries Xte (m, d) and k, return the (m,) predicted labels:

• take a majority vote over the k nearest neighbours in Euclidean distance
• break vote ties in favour of the smallest class label

Input

Xtr =
[[0. 0.]
 [1. 0.]
 [5. 5.]
 [6. 5.]]
ytr = [0 0 1 1]
Xte =
[[0.5 0. ]
 [5.5 5. ]]
k = 3

Output

[0 1]