Дан набор точек и k центров кластеров. Для каждой точки определите номер ближайшего центра (нумерация с 0). Расстояние между точками считается евклидовым. Если точка имеет одинаковое минимальное расстояние для двух и более кластеров, то ее необходимо определить к кластеру с наименьшим номером.
Формат входных данных:
Первая строка: n — количество точек (1 ≤ n ≤ 1000). Следующие n строк: xi yi — координаты i-й точки (целые числа, |xi|, |yi| ≤ 10000) Следующая строка: k — количество центров (1 ≤ k ≤ 10) Следующие k строк: cxi cyi — координаты j-го центра (целые числа, |cxi|, |cyi| ≤ 10000)
Формат выходных данных:
Одна строка с n числами — номера ближайших центров для каждой точки (0 ≤ номер < k)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 1
1 9
9 1
9 9
2
2 2
8 8
|
0 0 0 1
|