После длительного исследования и ряда экспериментов ведущая автомобилестроительная компания Мегаполии «АвтоВоз» выпустила уникальный по своим характеристикам автомобиль «Лада Малина». Одно из самых интересных нововведений «Лады Малины» — экологичные высокоэффективные двигатели.
Будем считать автомобиль точкой на плоскости Oxy. Автомобиль оснащен k двигателями, пронумерованными от 1 до k. Каждый двигатель имеет свой вектор скорости, который имеет координаты (vxi, vyi), измеряемые в единицах расстояния в день. Любой двигатель можно включить на любую мощность wi, которая является вещественным числом от - 1 до + 1 (включительно), что даёт вклад в (wi·vxi, wi·vyi) к итоговому вектору скорости автомобиля. А именно, итоговый вектор скорости автомобиля оказывается равен
(w1·vx1 + w2·vx2 + ... + wk·vxk, w1·vy1 + w2·vy2 + ... + wk·vyk) Это означает, что если автомобиль перемещается с постоянными wi в течение дня, то x-координата автомобиля изменится на первую компоненту выражения выше, а y-координата автомобиля изменится на вторую компоненту выражения выше. Таким образом, если, например, все wi будут равны нулю, то автомобиль будет стоять на месте, а если все wi будут равны нулю, кроме w1 = 1, то автомобиль поедет со скоростью, задаваемой вектором скорости первого двигателя.
В Мегаполии имеются n фабрик, i-я расположена в точке (fxi, fyi). На i-й фабрике изготовлено ai автомобилей «Лада Малина», полностью готовых к поездкам.
Для продвижения новой модели «АвтоВоз» хочет устроить международную выставку-показ автомобилей. Имеется q вариантов местоположения и времени проведения выставки, в i-м из них выставка пройдёт в точке с координатами (pxi, pyi) через ti дней.
Конечно, на место проведения выставки «АвтоВоз» хотел бы привезти как можно больше автомобилей с фабрик. Перемещение автомобиля происходит путём включения его двигателей с произвольными значениями мощности, в результате чего ровно к моменту начала выставки автомобиль должен оказаться в точке местоположения выставки.
Однако, при разных вариантах проведения выставки может оказаться невозможным успеть перегнать автомобили с той или иной фабрики к началу выставки. Поэтому вам предлагается определить для каждого из вариантов местоположения и времени выставки, сколько автомобилей со всех фабрик смогут успеть к её началу.
Примечание
Изображения, относящиеся к тестам из условия, даны ниже. Варианты местоположения выставки отмечены крестиками, а фабрики точками. Рядом с каждой фабрикой указано количество автомобилей, находящихся на ней.
Пояснение к первому примеру:
- Автомобиль с первой фабрики не успеет добраться до места проведения.
- Автомобиль со второй фабрики можно перегнать, если установить значения w1 = 0, w2 = 1.
- Автомобиль с третьей фабрики можно перегнать, если установить значения
, 
. - Автомобиль с четвёртой фабрики можно перегнать, если установить значения w1 = 1, w2 = 0.
