Новые центры групп поездок велопроката

Городской велопрокат анализирует характеристики завершённых поездок. Каждая поездка описывается двумя величинами: длительностью в секундах и длиной маршрута в метрах.

Для разделения поездок на группы используется одна итерация метода k-means. Сначала каждая поездка с известными обеими характеристиками относится к ближайшему исходному центру. Затем для каждой группы вычисляется новый центр.

Квадрат расстояния между поездкой с координатами (x, y) и центром (a, b) равен (x-a)^2 + (y-b)^2. Поездка относится к центру с наименьшим квадратом расстояния. Новый центр группы равен среднему арифметическому координат всех поездок, отнесённых к этой группе.

Строка поездки, в которой хотя бы одна характеристика равна NA, не участвует ни в распределении по группам, ни в вычислении новых центров. Если расстояния до нескольких центров равны, поездка относится к центру с меньшим номером. Гарантируется, что после исключения строк с NA в каждой группе будет хотя бы одна поездка.

В конце входных данных заданы номера центров, для которых требуется вывести координаты после одной итерации.

Формат ввода

В первой строке даны три целых числа n, k и q — количество записей о поездках, количество исходных центров и количество запросов.

В следующих n строках записаны длительность и длина одной поездки. Каждое значение является целым числом либо строкой NA.

В следующих k строках записаны по два целых числа — длительность и длина исходного центра. Центры пронумерованы от 1 до k в порядке их появления во входе.

В последних q строках записаны номера запрошенных центров.

Формат вывода

Для каждого запроса выведите в отдельной строке две координаты нового центра: среднюю длительность и среднюю длину маршрута.

Каждую координату выведите ровно с двумя знаками после точки. Значение округляется до ближайшей сотой, а при точном равенстве между двумя сотыми выбирается большая.

Ограничения

1 ≤ n ≤ 2000.

1 ≤ k ≤ 20, 1 ≤ q ≤ 100.

1 ≤ k ≤ n.

Каждая известная длительность поездки и каждого центра находится в диапазоне от 60 до 7200 секунд.

Каждая известная длина маршрута и каждого центра находится в диапазоне от 100 до 30000 метров.

Значение NA имеет длину 2, целые значения содержат от 2 до 5 символов.

Номер каждого запроса находится в диапазоне от 1 до k.