CF853E.Lada Malina

After long-term research and lots of experiments leading Megapolian automobile manufacturer «AutoVoz» released a brand new car model named «Lada Malina». One of the most impressive features of «Lada Malina» is its highly efficient environment-friendly engines.

Consider car as a point in Oxy plane. Car is equipped with k engines numbered from 1 to k. Each engine is defined by its velocity vector whose coordinates are (vx__i, vy__i) measured in distance units per day. An engine may be turned on at any level w__i, that is a real number between  - 1 and  + 1 (inclusive) that result in a term of (w__i·vx__i, w__i·vy__i) in the final car velocity. Namely, the final car velocity is equal to

(_w_1·_vx_1 + _w_2·_vx_2 + ... + w__k·vx__k,  _w_1·_vy_1 + _w_2·_vy_2 + ... + w__k·vy__k)

Formally, if car moves with constant values of w__i during the whole day then its x-coordinate will change by the first component of an expression above, and its y-coordinate will change by the second component of an expression above. For example, if all w__i are equal to zero, the car won't move, and if all w__i are equal to zero except _w_1 = 1, then car will move with the velocity of the first engine.

There are n factories in Megapolia, i-th of them is located in (fx__i, fy__i). On the i-th factory there are a__i cars «Lada Malina» that are ready for operation.

As an attempt to increase sales of a new car, «AutoVoz» is going to hold an international exposition of cars. There are q options of exposition location and time, in the i-th of them exposition will happen in a point with coordinates (px__i, py__i) in t__i days.

Of course, at the «AutoVoz» is going to bring as much new cars from factories as possible to the place of exposition. Cars are going to be moved by enabling their engines on some certain levels, such that at the beginning of an exposition car gets exactly to the exposition location.

However, for some of the options it may be impossible to bring cars from some of the factories to the exposition location by the moment of an exposition. Your task is to determine for each of the options of exposition location and time how many cars will be able to get there by the beginning of an exposition.

经过长期研究和大量实验，梅加波利亚汽车制造商「AutoVoz」推出了一款全新车型——「拉达·马林娜（Lada Malina）」。该车型最令人印象深刻的特点之一，是其高效且环境友好的发动机系统。

将汽车视为 $Oxy$ 平面上的一个点。该汽车配备了 $k$ 台编号为 $1$ 至 $k$ 的发动机。每台发动机由其速度向量定义，其坐标为 $(vx_i,\,vy_i)$，单位为「距离单位/天」。每台发动机可被设定在任意档位 $w_i$ 下运行，其中 $w_i$ 是介于 $-1$ 与 $+1$（含端点）之间的实数；该档位会使汽车最终速度中增加一项 $(w_i\cdot vx_i,\,w_i\cdot vy_i)$。换言之，汽车的最终速度为：

$$(w_1\cdot vx_1\,+\,w_2\cdot vx_2\,+\,\dots\,+\,w_k\cdot vx_k,\; w_1\cdot vy_1\,+\,w_2\cdot vy_2\,+\,\dots\,+\,w_k\cdot vy_k)$$

形式化地说：若汽车在整日中均以恒定的 $w_i$ 值运行，则其 $x$ 坐标的变化量等于上述表达式的第一个分量，其 $y$ 坐标的变化量等于第二个分量。例如，若所有 $w_i$ 均为 $0$，则汽车静止不动；若仅 $w_1 = 1$ 而其余 $w_i = 0$，则汽车将以第一台发动机的速度运动。

梅加波利亚境内共有 $n$ 座工厂，第 $i$ 座工厂位于坐标 $(fx_i,\,fy_i)$ 处；第 $i$ 座工厂有 $a_i$ 辆已准备就绪、可立即投入运行的「拉达·马林娜」汽车。

为提升这款新车的销量，「AutoVoz」计划举办一场国际汽车博览会。博览会共提供 $q$ 种选址与时间方案：第 $i$ 种方案对应于在 $t_i$ 天后、于坐标 $(px_i,\,py_i)$ 处举行博览会。

当然，「AutoVoz」将尽可能多地从各工厂调运新车前往博览会现场。调运方式是通过为每辆汽车的发动机设定合适的档位 $w_i$，使得汽车恰好在博览会开始时刻抵达博览会地点。

然而，对某些选址与时间方案而言，可能无法使来自某些工厂的汽车在博览会开始前抵达现场。你的任务是：对每一种博览会选址与时间方案，计算出能在博览会开始时刻抵达现场的汽车总数。

The first line of input contains three integers k, n, q (2 ≤ k ≤ 10, 1 ≤ n ≤ 105, 1 ≤ q ≤ 105), the number of engines of «Lada Malina», number of factories producing «Lada Malina» and number of options of an exposition time and location respectively.

The following k lines contain the descriptions of «Lada Malina» engines. The i-th of them contains two integers vx__i, vy__i ( - 1000 ≤ vx__i, vy__i ≤ 1000) defining the velocity vector of the i-th engine. Velocity vector can't be zero, i.e. at least one of vx__i and vy__i is not equal to zero. It is guaranteed that no two velosity vectors are collinear (parallel).

Next n lines contain the descriptions of factories. The i-th of them contains two integers fx__i, fy__i, a__i ( - 109 ≤ fx__i, fy__i ≤ 109, 1 ≤ a__i ≤ 109) defining the coordinates of the i-th factory location and the number of cars that are located there.

The following q lines contain the descriptions of the car exposition. The i-th of them contains three integers px__i, py__i, t__i ( - 109 ≤ px__i, py__i ≤ 109, 1 ≤ t__i ≤ 105) defining the coordinates of the exposition location and the number of days till the exposition start in the i-th option.

输入的第一行包含三个整数 $k$、$n$、$q$（$2 \le k \le 10$，$1 \le n \le 10^5$，$1 \le q \le 10^5$），分别表示「拉达·马利纳」（Lada Malina）汽车的发动机数量、生产该车型的工厂数量，以及车展时间与地点的可选方案数量。

接下来的 $k$ 行描述了「拉达·马利纳」的发动机。其中第 $i$ 行包含两个整数 $vx_i$、$vy_i$（$-1000 \le vx_i, vy_i \le 1000$），定义第 $i$ 台发动机的速度向量。速度向量不能为零向量，即 $vx_i$ 与 $vy_i$ 中至少有一个不等于零。保证任意两个速度向量均不共线（即不平行）。

接下来的 $n$ 行描述了各工厂的信息。其中第 $i$ 行包含三个整数 $fx_i$、$fy_i$、$a_i$（$-10^9 \le fx_i, fy_i \le 10^9$，$1 \le a_i \le 10^9$），分别表示第 $i$ 家工厂的坐标及其所拥有的汽车数量。

接下来的 $q$ 行描述了车展安排。其中第 $i$ 行包含三个整数 $px_i$、$py_i$、$t_i$（$-10^9 \le px_i, py_i \le 10^9$，$1 \le t_i \le 10^5$），分别表示第 $i$ 种方案中车展的举办地点坐标，以及距离该车展开始的天数。

For each possible option of the exposition output the number of cars that will be able to get to the exposition location by the moment of its beginning.

对于每种可能的展览方案，输出在展览开始时刻能够到达展览地点的汽车数量。

Images describing sample tests are given below. Exposition options are denoted with crosses, factories are denoted with points. Each factory is labeled with a number of cars that it has.

First sample test explanation:

• Car from the first factory is not able to get to the exposition location in time.
• Car from the second factory can get to the exposition in time if we set _w_1 = 0, _w_2 = 1.
• Car from the third factory can get to the exposition in time if we set , .
• Car from the fourth factory can get to the exposition in time if we set _w_1 = 1, _w_2 = 0.

下方给出了描述样例测试的图片。展览地点用“×”表示，工厂用“·”表示。每个工厂均标有其拥有的汽车数量。

第一个样例测试的解释：

• 来自第一个工厂的汽车无法及时到达展览地点。
• 来自第二个工厂的汽车可在设置 $w_1 = 0$、$w_2 = 1$ 时及时到达展览地点。
• 来自第三个工厂的汽车可在设置 、 时及时到达展览地点。
• 来自第四个工厂的汽车可在设置 $w_1 = 1$、$w_2 = 0$ 时及时到达展览地点。