Електричне забруднення
Сортонія — столиця провінції Північна Нлогонія. Місто сплановане у вигляді квадратної сітки, де вулиці орієнтовані або в напрямку Північ-Південь, або Захід-Схід. Виняток становить Проспект Злиття, який проходить з Південного Заходу на Північний Схід, розділяючи квартали по діагоналі.
Сортонія також є одним з найзеленіших міст Нлогонії. Місцевий університет розробив технологію, яка використовує магнітне поле Землі для генерації енергії. Як наслідок, на всіх перехрестях Проспекту Злиття встановлені генератори, що постачають електроенергію всім будинкам і підприємствам міста.
Цю технологію високо оцінили екологи, адже вона усунула вуглецевий слід Сортонії. Проте, незабаром після її впровадження, в місті було знайдено тисячі мертвих бджіл і птахів. Здивована, королева Нлогонії наказала біофізикам королівства розслідувати це явище.
Після багатьох місяців досліджень вони виявили, що генератори в Сортонії створюють аномалії в місцевому магнітному полі. Птахи і бджоли, які використовують магнітне поле Землі для навігації, були збентежені цими аномаліями, почали літати по колу і зрештою загинули від виснаження.
Згідно з теоретичними моделями біофізиків, кожен генератор створює аномалію, яка представлена цілим числом. Кожна аномалія поширюється нескінченно в усіх чотирьох напрямках компаса. Точки, які не знаходяться безпосередньо на північ, південь, захід або схід від генератора, не зазнають впливу. Якщо точка вирівняна з двома генераторами, то аномалія в цій точці є сумою аномалій, створених цими генераторами. Наприклад, розглянемо малюнок нижче, який представляє певну частину Сортонії. Аномалія в точці 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-й запит. Якщо інформації, наданої вимірюваннями, достатньо для прогнозування аномалії в запитуваній точці, то напишіть ціле число, що представляє передбачену аномалію в запитуваній точці. В іншому випадку напишіть символ '*' (зірочка). Надрукуйте рядок, що містить один символ '-' (дефіс) після кожного тестового випадку.