{"raw_statement":[{"iden":"statement","content":"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.\n\nConsider 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\n\n(_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.\n\nThere 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.\n\nAs 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.\n\nOf 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.\n\nHowever, 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."},{"iden":"input","content":"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.\n\nThe 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).\n\nNext _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.\n\nThe 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."},{"iden":"output","content":"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."},{"iden":"examples","content":"Input\n\n2 4 1\n1 1\n-1 1\n2 3 1\n2 -2 1\n-2 1 1\n-2 -2 1\n0 0 2\n\nOutput\n\n3\n\nInput\n\n3 4 3\n2 0\n-1 1\n-1 -2\n-3 0 6\n1 -2 1\n-3 -7 3\n3 2 2\n-1 -4 1\n0 4 2\n6 0 1\n\nOutput\n\n4\n9\n0"},{"iden":"note","content":"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.\n\nFirst sample test explanation:\n\n* Car from the first factory is not able to get to the exposition location in time.\n* Car from the second factory can get to the exposition in time if we set _w_1 = 0, _w_2 = 1.\n* Car from the third factory can get to the exposition in time if we set , .\n* Car from the fourth factory can get to the exposition in time if we set _w_1 = 1, _w_2 = 0.\n\n "}],"translated_statement":[{"iden":"statement","content":"经过长期的研究和大量实验，Megapolia 汽车制造商 «AutoVoz» 推出了一个全新的汽车型号，名为 «Lada Malina»。该车最令人印象深刻的特性之一是其高效环保的发动机系统。\n\n将汽车视为 Oxy 平面上的一个点。汽车配备了编号为 1 到 k 的 k 个发动机。每个发动机由其速度向量定义，坐标为 (vxi, vyi)，单位为距离单位/天。每个发动机可以以任意级别 wi 启动，其中 wi 是介于 -1 和 +1 之间的实数（含端点），该级别会产生一个贡献项 (wi·vxi, wi·vyi) 到最终的汽车速度。因此，汽车的最终速度等于：\n\n形式上，如果汽车在整个一天内保持 wi 的值不变，则其 x 坐标的变化量等于上述表达式的第一个分量，y 坐标的变化量等于第二个分量。例如，若所有 wi 均为零，则汽车不会移动；若除 w1 = 1 外所有 wi 均为零，则汽车将以第一个发动机的速度移动。\n\nMegapolia 共有 n 个工厂，第 i 个工厂位于 (fxi, fyi)。每个工厂 i 上有 ai 辆已准备就绪的 «Lada Malina» 汽车。\n\n为了促进新车销售，«AutoVoz» 将举办一场国际汽车博览会。博览会共有 q 种可能的地点与时间方案，第 i 种方案中，博览会将在坐标为 (pxi, pyi) 的地点于 ti 天后举行。\n\n显然，«AutoVoz» 希望尽可能多地从各个工厂将新车运送到博览会地点。汽车通过设定发动机的特定级别来移动，使得在博览会开始时，汽车恰好到达博览会地点。\n\n然而，对于某些方案，可能无法在博览会开始前将某些工厂的汽车运送到博览会地点。你的任务是：对于每种博览会地点与时间的方案，确定有多少辆汽车能够在博览会开始前抵达。\n\n输入的第一行包含三个整数 k, n, q（2 ≤ k ≤ 10，1 ≤ n ≤ 10^5，1 ≤ q ≤ 10^5），分别表示 «Lada Malina» 的发动机数量、生产 «Lada Malina» 的工厂数量以及博览会时间与地点的方案数量。\n\n接下来的 k 行描述 «Lada Malina» 的发动机。第 i 行包含两个整数 vxi, vyi（-1000 ≤ vxi, vyi ≤ 1000），定义第 i 个发动机的速度向量。速度向量不能为零，即 vxi 和 vyi 至少有一个不为零。保证任意两个速度向量不共线（不平行）。\n\n接下来的 n 行描述工厂。第 i 行包含三个整数 fxi, fyi, ai（-10^9 ≤ fxi, fyi ≤ 10^9，1 ≤ ai ≤ 10^9），分别表示第 i 个工厂的位置坐标和该厂拥有的汽车数量。\n\n接下来的 q 行描述博览会方案。第 i 行包含三个整数 pxi, pyi, ti（-10^9 ≤ pxi, pyi ≤ 10^9，1 ≤ ti ≤ 10^5），分别表示博览会地点的坐标和该方案中距离博览会开始的天数。\n\n对于每种博览会方案，请输出能够在博览会开始前抵达该地点的汽车数量。\n\n下图展示了样例测试的说明。博览会方案用叉号表示，工厂用点表示，每个工厂旁标注了其拥有的汽车数量。\n\n第一个样例测试说明：","input":"The first line of input contains three integers #cf_span[k, n, q] (#cf_span[2 ≤ k ≤ 10], #cf_span[1 ≤ n ≤ 105], #cf_span[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 #cf_span[k] lines contain the descriptions of «Lada Malina» engines. The #cf_span[i]-th of them contains two integers #cf_span[vxi], #cf_span[vyi] (#cf_span[ - 1000 ≤ vxi, vyi ≤ 1000]) defining the velocity vector of the #cf_span[i]-th engine. Velocity vector can't be zero, i.e. at least one of #cf_span[vxi] and #cf_span[vyi] is not equal to zero. It is guaranteed that no two velosity vectors are collinear (parallel).Next #cf_span[n] lines contain the descriptions of factories. The #cf_span[i]-th of them contains two integers #cf_span[fxi], #cf_span[fyi], #cf_span[ai] (#cf_span[ - 109 ≤ fxi, fyi ≤ 109], #cf_span[1 ≤ ai ≤ 109]) defining the coordinates of the #cf_span[i]-th factory location and the number of cars that are located there.The following #cf_span[q] lines contain the descriptions of the car exposition. The #cf_span[i]-th of them contains three integers #cf_span[pxi], #cf_span[pyi], #cf_span[ti] (#cf_span[ - 109 ≤ pxi, pyi ≤ 109], #cf_span[1 ≤ ti ≤ 105]) defining the coordinates of the exposition location and the number of days till the exposition start in the #cf_span[i]-th option.","output":"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.","examples":"Input2 4 11 1-1 12 3 12 -2 1-2 1 1-2 -2 10 0 2Output3Input3 4 32 0-1 1-1 -2-3 0 61 -2 1-3 -7 33 2 2-1 -4 10 4 26 0 1Output490","note":"下图展示了样例测试的说明。博览会方案用叉号表示，工厂用点表示，每个工厂旁标注了其拥有的汽车数量。\n第一个样例测试说明：\n第一工厂的汽车无法在规定时间内抵达博览会地点。\n第二工厂的汽车可以通过设置 w1 = 0，w2 = 1 在规定时间内抵达。\n第三工厂的汽车可以通过设置 ， 在规定时间内抵达。\n第四工厂的汽车可以通过设置 w1 = 1，w2 = 0 在规定时间内抵达。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions:**\n\n- Let $ \\mathbf{v}_i = (v_{xi}, v_{yi}) \\in \\mathbb{R}^2 $, $ i = 1, \\dots, k $, be the velocity vectors of the $ k $ engines. \n- Let $ w_i \\in [-1, 1] $ be the activation level of engine $ i $. \n- The car’s net velocity is $ \\sum_{i=1}^k w_i \\mathbf{v}_i $. \n- Let $ \\mathbf{d} = (d_x, d_y) \\in \\mathbb{R}^2 $ be the displacement vector a car must achieve in $ t $ days: $ \\mathbf{d} = t \\cdot \\sum_{i=1}^k w_i \\mathbf{v}_i $. \n- Let $ \\mathbf{f}_j = (f_{xj}, f_{yj}) \\in \\mathbb{R}^2 $, $ j = 1, \\dots, n $, be the location of factory $ j $. \n- Let $ a_j \\in \\mathbb{Z}^+ $ be the number of cars at factory $ j $. \n- Let $ \\mathbf{p}_m = (p_{xm}, p_{ym}) \\in \\mathbb{R}^2 $, $ t_m \\in \\mathbb{Z}^+ $, $ m = 1, \\dots, q $, be the exposition location and time for option $ m $. \n\n**Given Constraints:**\n\n- The set $ \\{\\mathbf{v}_1, \\dots, \\mathbf{v}_k\\} $ is linearly independent in $ \\mathbb{R}^2 $ (since $ k \\geq 2 $ and no two vectors are collinear). \n- For any displacement $ \\mathbf{d} \\in \\mathbb{R}^2 $, there exists a unique solution $ \\mathbf{w} = (w_1, \\dots, w_k) \\in \\mathbb{R}^k $ such that: \n $$\n \\sum_{i=1}^k w_i \\mathbf{v}_i = \\frac{\\mathbf{d}}{t}\n $$\n because $ \\{\\mathbf{v}_i\\} $ spans $ \\mathbb{R}^2 $ and $ k \\geq 2 $. \n- The feasibility condition is: $ w_i \\in [-1, 1] $ for all $ i = 1, \\dots, k $. \n\n**Objective:**\n\nFor each exposition option $ m $, compute: \n$$\n\\sum_{\\substack{j=1 \\\\ \\exists \\mathbf{w} \\in [-1,1]^k : \\sum_{i=1}^k w_i \\mathbf{v}_i = \\frac{\\mathbf{p}_m - \\mathbf{f}_j}{t_m}}}^n a_j\n$$\n\nThat is, sum the number of cars at factories $ j $ for which the displacement vector $ \\mathbf{p}_m - \\mathbf{f}_j $ is reachable in $ t_m $ days using engine activation levels $ w_i \\in [-1,1] $.\n\n**Formal Statement:**\n\nLet $ \\mathbf{V} \\in \\mathbb{R}^{2 \\times k} $ be the matrix whose columns are $ \\mathbf{v}_1, \\dots, \\mathbf{v}_k $. \nFor exposition option $ m $, define target velocity: \n$$\n\\mathbf{u}_m = \\frac{\\mathbf{p}_m - \\mathbf{f}_j}{t_m}\n$$\n\nThe displacement from factory $ j $ to exposition $ m $ is achievable if and only if the linear system: \n$$\n\\mathbf{V} \\mathbf{w} = \\mathbf{u}_m\n$$\nhas a solution $ \\mathbf{w} = (w_1, \\dots, w_k)^\\top \\in [-1, 1]^k $.\n\nSince $ \\mathbf{V} $ has full row rank (2), the solution space is affine of dimension $ k-2 $. But because $ k \\leq 10 $, and the system is underdetermined, we can compute the unique solution in the 2D span (via pseudoinverse or basis projection), and check if the resulting $ \\mathbf{w} $ lies in $ [-1,1]^k $.\n\nHowever, note: **for each factory-exposition pair**, the required velocity $ \\mathbf{u}_m $ is fixed. The system $ \\mathbf{V} \\mathbf{w} = \\mathbf{u}_m $ has a solution if and only if $ \\mathbf{u}_m \\in \\text{span}(\\mathbf{v}_1, \\dots, \\mathbf{v}_k) = \\mathbb{R}^2 $, which is always true. So the only constraint is whether the **unique** (in the 2D subspace) solution $ \\mathbf{w} $ satisfies $ w_i \\in [-1,1] $ for all $ i $.\n\nBut since $ k > 2 $, the solution is **not unique**. The system $ \\mathbf{V} \\mathbf{w} = \\mathbf{u}_m $ has infinitely many solutions in $ \\mathbb{R}^k $. The set of feasible $ \\mathbf{w} $ is a $ (k-2) $-dimensional affine subspace intersected with the hypercube $ [-1,1]^k $.\n\nThus, the problem reduces to: \nFor each factory $ j $ and exposition $ m $, determine whether the affine subspace \n$$\n\\mathcal{S}_{jm} = \\left\\{ \\mathbf{w} \\in \\mathbb{R}^k \\mid \\mathbf{V} \\mathbf{w} = \\frac{\\mathbf{p}_m - \\mathbf{f}_j}{t_m} \\right\\}\n$$\nhas non-empty intersection with $ [-1,1]^k $.\n\nThis is a **linear feasibility problem** in $ k $ variables with 2 linear equality constraints and $ 2k $ box constraints.\n\n**Final Formal Output:**\n\nFor each exposition option $ m \\in \\{1, \\dots, q\\} $, output: \n$$\n\\sum_{j=1}^{n} a_j \\cdot \\mathbb{I}\\left( \\exists \\mathbf{w} \\in [-1,1]^k \\text{ s.t. } \\mathbf{V} \\mathbf{w} = \\frac{\\mathbf{p}_m - \\mathbf{f}_j}{t_m} \\right)\n$$\n\nwhere $ \\mathbb{I}(\\cdot) $ is the indicator function.","simple_statement":null,"has_page_source":false}