После длительного исследования и ряда экспериментов ведущая автомобилестроительная компания Мегаполии «АвтоВоз» выпустила уникальный по своим характеристикам автомобиль «Лада Малина». Одно из самых интересных нововведений «Лады Малины» — экологичные высокоэффективные двигатели.
Будем считать автомобиль точкой на плоскости Oxy. Автомобиль оснащен k двигателями, пронумерованными от 1 до k. Каждый двигатель имеет свой вектор скорости, который имеет координаты (vxi, vyi), измеряемые в единицах расстояния в день. Любой двигатель можно включить на любую мощность wi, которая является вещественным числом от - 1 до + 1 (включительно), что даёт вклад в (wi·vxi, wi·vyi) к итоговому вектору скорости автомобиля. А именно, итоговый вектор скорости автомобиля оказывается равен
Это означает, что если автомобиль перемещается с постоянными wi в течение дня, то x-координата автомобиля изменится на первую компоненту выражения выше, а y-координата автомобиля изменится на вторую компоненту выражения выше. Таким образом, если, например, все wi будут равны нулю, то автомобиль будет стоять на месте, а если все wi будут равны нулю, кроме w1 = 1, то автомобиль поедет со скоростью, задаваемой вектором скорости первого двигателя.
В Мегаполии имеются n фабрик, i-я расположена в точке (fxi, fyi). На i-й фабрике изготовлено ai автомобилей «Лада Малина», полностью готовых к поездкам.
Для продвижения новой модели «АвтоВоз» хочет устроить международную выставку-показ автомобилей. Имеется q вариантов местоположения и времени проведения выставки, в i-м из них выставка пройдёт в точке с координатами (pxi, pyi) через ti дней.
Конечно, на место проведения выставки «АвтоВоз» хотел бы привезти как можно больше автомобилей с фабрик. Перемещение автомобиля происходит путём включения его двигателей с произвольными значениями мощности, в результате чего ровно к моменту начала выставки автомобиль должен оказаться в точке местоположения выставки.
Однако, при разных вариантах проведения выставки может оказаться невозможным успеть перегнать автомобили с той или иной фабрики к началу выставки. Поэтому вам предлагается определить для каждого из вариантов местоположения и времени выставки, сколько автомобилей со всех фабрик смогут успеть к её началу.
В первой строке находятся три целых числа k, n, q (2 ≤ k ≤ 10, 1 ≤ n ≤ 105, 1 ≤ q ≤ 105) — количество двигателей у автомобиля «Лада Малина», количество фабрик по производству «Лады Малины» и количество вариантов местоположения и времени проведения международной выставки-показа автомобилей соответственно.
В следующих k строках находятся описания двигателей «Лады Малины», в i-й из них находятся два целых числа vxi, vyi ( - 1000 ≤ vxi, vyi ≤ 1000), задающих вектор скорости i-го двигателя. Вектор скорости не может быть нулевым, то есть, vxi и vyi не равны одновременно нулю. Гарантируется, что никакие два из векторов скоростей не коллинеарны (параллельны).
Следующие n строк содержат описания фабрик. В i-й из них находятся три целых числа fxi, fyi, ai ( - 109 ≤ fxi, fyi ≤ 109, 1 ≤ ai ≤ 109), координаты i-й фабрики и количество автомобилей на ней соответственно.
Следующие q строках содержат описания местоположений выставок. В i-й из них находятся три целых числа pxi, pyi, ti ( - 109 ≤ pxi, pyi ≤ 109, 1 ≤ ti ≤ 105), координаты i-го местоположения выставки и количество дней до её проведения соответственно.
Для каждого возможного варианта местоположения выведите число автомобилей, которые смогут к времени проведения выставки добраться до неё.
2 4 1
1 1
-1 1
2 3 1
2 -2 1
-2 1 1
-2 -2 1
0 0 2
3
3 4 3
2 0
-1 1
-1 -2
-3 0 6
1 -2 1
-3 -7 3
3 2 2
-1 -4 1
0 4 2
6 0 1
4
9
0
Изображения, относящиеся к тестам из условия, даны ниже. Варианты местоположения выставки отмечены крестиками, а фабрики точками. Рядом с каждой фабрикой указано количество автомобилей, находящихся на ней.
Пояснение к первому примеру:
- Автомобиль с первой фабрики не успеет добраться до места проведения.
- Автомобиль со второй фабрики можно перегнать, если установить значения w1 = 0, w2 = 1.
- Автомобиль с третьей фабрики можно перегнать, если установить значения
, 
. - Автомобиль с четвёртой фабрики можно перегнать, если установить значения w1 = 1, w2 = 0.
