Расследование киберпреступлений с пончиками
Год 2042. Интернет превратился в виртуальную реальность, где ежедневно происходят преступления. Победитель SWERC 2041 года создал агента, который оставляет пончик каждый раз, когда в киберпространстве совершается преступление. У каждого пончика есть уникальная подпись. Полиция Мадрида располагает обширной базой данных с преступлениями и их пончиковыми подписями.
Сегодня ваш день. Ваша задача — разработать нового агента, который будет искать в базе данных записи, максимально похожие на подпись пончика, найденного на новом месте преступления.
Рисунок 2: Основное доказательство сегодняшней нераскрытой серии преступлений
Эксперты в области виртуальной криминологии определили наилучшую меру сходства между пончиками: нужно вычислить разницу в радиусе внутренней части тороидов (отверстий), затем разницу в радиусе внешней части тороидов (трубок), и сложить эти разницы.
Входные данные
Первая строка каждого тестового случая содержит n (1 ≤ n ≤ 100000), количество пончиков в базе данных. i^th из следующих n строк содержит радиус отверстия и радиус трубки i^th пончика в базе данных, представленных двумя целыми числами l и w (1 ≤ l, w ≤ 10^9). Далее следует строка, содержащая q (1 ≤ q ≤ 50000), количество пончиков, которые вы ищете в базе данных. Затем идут q строк, каждая из которых описывает размеры вновь найденного i^th пончика таким же образом.
Разные тестовые случаи разделяются пустой строкой. Строка, содержащая -1, указывает на конец ввода.
Выходные данные
Вывод вашей программы для каждого тестового случая должен содержать q строк, каждая из которых содержит целое число. i^th из этих строк должна содержать сходство между вновь найденным i^th пончиком и наиболее похожим на него пончиком из базы данных. Выводы для разных тестовых случаев должны быть разделены пустой строкой.