Электрическое загрязнение
Сортонія — столица провинции Северная Нлогония. Город спроектирован так, что почти все его улицы образуют квадратную сетку, ориентированную в направлениях Север-Юг или Запад-Восток. Единственным исключением является Проспект Слияния, который проходит с Юго-Запада на Северо-Восток, разделяя городские кварталы по диагонали.
Сортонія также является одним из самых зелёных городов Нлогонии. Местный университет разработал технологию использования магнитного поля Земли для генерации энергии. В результате на всех перекрёстках Проспекта Слияния установлены генераторы, которые обеспечивают электроэнергией все дома и предприятия города.
Эта технология была высоко оценена экологами за устранение углеродного следа Сортонии, но вскоре после её внедрения в городе были найдены тысячи мёртвых пчёл и птиц. Удивлённая, королева Нлогонии приказала биофизикам королевства расследовать это явление.
После многих месяцев исследований они обнаружили, что генераторы, используемые в Сортонии, создают аномалии в местном магнитном поле. Птицы и пчёлы, которые используют магнитное поле Земли для ориентации во время полёта, были сбиты с толку этими аномалиями, начинали летать по кругу и в конечном итоге погибали от истощения.
Согласно теоретическим моделям биофизиков, каждый генератор создаёт аномалию, которая представляется целым числом. Каждая аномалия распространяется бесконечно во всех четырёх направлениях компаса. Точки, которые не находятся прямо на север, юг, запад или восток от генератора, не подвергаются воздействию. С другой стороны, если точка выровнена с двумя генераторами, то аномалия в этой точке является суммой двух аномалий, созданных этими генераторами. Например, рассмотрите изображение ниже, которое представляет определённую часть Сортонии. Аномалия в точке R — это только та, что создана генератором в этой точке, тогда как аномалия в точке T является суммой аномалий, созданных генератором в точке R и генератором в точке S.
Биофизики хотели бы измерить аномалии на некоторых городских перекрёстках, но эти измерения требуют дорогого оборудования и технической экспертизы. Поэтому они планируют измерить лишь подмножество городских перекрёстков и экстраполировать остальные данные из них. Прогнозирование аномалии из набора измерений может требовать комбинирования нескольких из них сложными способами. Таким образом, королева поручила вам написать программу, которая прогнозирует аномалии на определённых перекрёстках, учитывая ранее сделанные измерения.
Входные данные
Каждый тестовый случай описывается несколькими строками. Первая строка содержит два целых числа M и Q, которые представляют соответственно количество измерений и количество запросов (1 ≤ M, Q ≤ 10^4). Каждая из следующих M строк описывает измерение с помощью трёх целых чисел X, Y и A, указывающих, что измеренная аномалия в точке (X, Y) равна A (-10^7 ≤ X, Y ≤ 10^7 и -10^4 ≤ A ≤ 10^4). После этого каждая из следующих Q строк описывает запрос с помощью двух целых чисел X_0 и Y_0, указывающих, что аномалия в точке (X_0, Y_0) должна быть предсказана (-10^7 ≤ X_0, Y_0 ≤ 10^7). Все позиции измеряются в городских кварталах; первая координата увеличивается с Запада на Восток, тогда как вторая координата увеличивается с Юга на Север. Точка (0, 0) находится на Проспекте Слияния. Вы можете предположить, что в каждом тестовом случае каждая точка не измеряется более одного раза. Также каждая точка не запрашивается более одного раза. Вы также можете предположить, что все измерения согласованы.
Последний тестовый случай сопровождается строкой, содержащей два нуля.
Выходные данные
Для каждого тестового случая выведите Q+1 строк. В i-й строке напишите ответ на i-й запрос. Если информации, предоставленной измерениями, достаточно для прогнозирования аномалии в запрашиваемой точке, то напишите целое число, представляющее предсказанную аномалию в запрашиваемой точке. В противном случае напишите символ '*' (звёздочка). Напечатайте строку, содержащую один символ '-' (дефис) после каждого тестового случая.