Сеть магазинов хочет заранее понять, будет ли у нового магазина высокая посещаемость. Для уже работающих магазинов известно число домохозяйств рядом xi и класс ci: 1 — посещаемость высокая, 0 — нет.
Для прогноза используется метод k ближайших соседей с голосованием. Чтобы предсказать класс нового магазина с числом домохозяйств x:
- для каждого известного магазина вычислим расстояние |xi − x|;
- упорядочим известные магазины по возрастанию расстояния; если расстояния равны, раньше идёт магазин, который стоит раньше во входных данных;
- возьмём первые k магазинов — это соседи;
- прогноз — тот класс, который встречается у соседей чаще. Так как k нечётно, ничьей не бывает.
Напишите программу, которая делает такой прогноз для нескольких новых магазинов. Пользоваться библиотеками машинного обучения нельзя — алгоритм нужно написать самостоятельно.
Входные данные
В первой строке даны два целых числа n и k — число известных магазинов и число соседей (1 ≤ k ≤ n ≤ 1000, k нечётно).
В каждой из следующих n строк даны два целых числа xi и ci — число домохозяйств рядом с магазином (0 ≤ xi ≤ 105) и его класс (ci равно 0 или 1).
В следующей строке дано целое число m — число новых магазинов (1 ≤ m ≤ 1000). В каждой из следующих m строк дано одно целое число x — число домохозяйств рядом с новым магазином (0 ≤ x ≤ 105).
Выходные данные
Для каждого нового магазина в порядке входных данных выведите в отдельной строке его класс: 0 или 1.
Пример
| Ввод |
Вывод |
4 3
1000 0
1400 0
1700 1
2300 1
2
1600
2100
|
0
1
|
Пояснение
Известны четыре магазина: (1000, 0), (1400, 0), (1700, 1), (2300, 1), k = 3.
Для x = 1600 расстояния равны 600, 200, 100, 700. Соседи — третий, второй и первый магазины, их классы 1, 0, 0. Нулей больше — ответ 0.
Для x = 2100 расстояния равны 1100, 700, 400, 200. Соседи — четвёртый, третий и второй магазины, их классы 1, 1, 0. Ответ 1.
Подсказка: если классы — это 0 и 1, то сумма классов соседей равна числу голосов «за 1». Класс 1 побеждает, если голосов больше k / 2.
| № | Входные данные | Выходные данные |
|
1
|
4 3
1000 0
1400 0
1700 1
2300 1
2
1600
2100
|
0
1
|