题目描述

给定一个长度为 $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<0$，否则 $f(k,A_i,B_i,C_i)=0$。定义集合 $S$ 为所有满足 $f(k,A_i,B_i,C_i)=1$ 的 $[l_k,r_k]$ 的并集内的整数组成的集合，求 $\sum_{k\in S} v_k$。

输入格式

第一行包含一个整数 $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$。

输出格式

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

0
5 2
2 2 4 4
-3 -3 1 1
-3 -1 3 5
1 -1 3 3
-2 3 1 5
12 3955 8019 1664 9231
2 -2 1
3 2 1

22881
18926

提示

样例 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）：无特殊限制。