P15871 【MX-X26-T7】「Cfz Round 7」**终极 AVX2 硬件指令提速**

给定一个长度为 $n$ 的数组 $v$ 和包含 $n$ 条「鱼鱼」的二维平面，第 $i$ 条「鱼鱼」的坐标是 $(x_i,y_i)$，有权值区间 $[l_i,r_i]$。 有 $m$ 个询问，每次询问给出 $A_i,B_i,C_i$。定义 $f(k,A_i,B_i,C_i)=1$ 当且仅当 $A_ix_k+B_iy_k+C_i

第一行包含一个整数 $c$，表示该测试点所属的子任务编号。样例满足 $c=0$。 第二行包含两个整数 $n,m$。 接下来 $n$ 行，第 $i$ 行包含四个整数 $x_i,y_i,l_i,r_i$。 接下来一行包含 $n$ 个整数 $v_1,\dots,v_n$。 接下来 $m$ 行，第 $i$ 行包含三个整数 $A_i,B_i,C_i$。

对于每个询问，输出一行，包含一个整数表示答案。

### 样例 1 解释 对于第 $1$ 个询问，只有第 $3$ 条「鱼鱼」和第 $5$ 条「鱼鱼」满足条件，它们的权值区间分别为 $[3,5]$ 和 $[1,5]$，因此 $S=\{1,2,3,4,5\}$，答案为 $v_1+v_2+v_3+v_4+v_5=22881$。 对于第 $2$ 个询问，只有第 $2$ 条「鱼鱼」和第 $3$ 条「鱼鱼」满足条件，它们的权值区间分别为 $[1,1]$ 和 $[3,5]$，因此 $S=\{1,3,4,5\}$，答案为 $v_1+v_3+v_4+v_5=18926$。 ### 数据范围 对于所有测试数据，均有： - $1\le n\le 5\cdot10^4$，$1\le m\le 5\cdot10^5$； - 对于所有 $1\le i \le n$，均有 $-10^6\le x_i,y_i\le 10^6$，$1\le l_i\le r_i\le n$； - 对于所有 $1 \le i \le n$，均有 $1 \le v_i \le 10^4$； - 对于所有 $1 \le i \le m$，均有 $-10^3\le A_i,B_i\le 10^3$，${A_i}^2+{B_i}^2>0$，$1 \le C_i\le10^9$； 对于除了 Subtask 2 以外的测试数据，保证 $n$ 条「鱼鱼」的 $x,y$ 坐标分别在某个预设的区间内均匀随机选取；并且，对于第 $i$ 条「鱼鱼」，$l_i,r_i$ 和 $x_i,y_i$ 是分别独立地随机选取的，但 $l_i,r_i$ 的分布没有特殊限制。 **本题采用捆绑测试。** - Subtask 1（10 points）：$n,m \le 10^3$。 - Subtask 2（18 points）：对于所有 $1 \le i \le n$，保证 $\max(|x_i|,|y_i|)=10^6$。 - Subtask 3（18 points）：对于所有 $1 \le i \le m$，保证 $|A_i|=|B_i|=1$。 - Subtask 4（24 points）：$n \le 2\cdot 10^4$，$m \le 2\cdot 10^5$。 - Subtask 5（30 points）：无特殊限制。