Implement a k-nearest neighbors (KNN) classifier from scratch in Python without using scikit-learn's KNN implementation. You are given training features X_train, training labels y_train, a test set X_test, and an integer k. Return the predicted class label for each test example in the same order as X_test. Use Euclidean distance by default: for two feature vectors a and b, the distance is sqrt(sum((a_i - b_i)^2)). For each test example, compute its distance to every training example, select the k training points with the smallest distances, and predict the label by majority vote among those neighbors. To make the result deterministic, if multiple classes receive the same highest vote count, return the smallest class label among the tied classes. Important discussion points for this problem: - Feature scaling matters in KNN because Euclidean distance is sensitive to magnitude. A feature with a large numeric range can dominate the distance unless the data is standardized or normalized. - KNN has almost no real training phase beyond storing the dataset, so training time is minimal compared with many other models. However, inference is expensive because each test point must be compared to all training points. - In practice, k is usually chosen using a validation set or cross-validation. Small k can overfit noise, while large k can oversmooth class boundaries. - Weighted KNN may be preferable when closer neighbors should influence the prediction more than farther neighbors, even if both are inside the top k.