Problem Description

Given an array $v$ of length $n$ and a 2D plane containing $n$ "fish", the coordinates of the $i$-th "fish" are $(x_i, y_i)$, with a weight interval $[l_i, r_i]$.

There are $m$ queries. Each query provides $A_i, B_i, C_i$. Define $f(k, A_i, B_i, C_i) = 1$ if and only if $A_i x_k + B_i y_k + C_i < 0$; otherwise, $f(k, A_i, B_i, C_i) = 0$. Define the set $S$ as the set of all integers that lie in the union of $[l_k, r_k]$ over all $k$ satisfying $f(k, A_i, B_i, C_i) = 1$. Compute $\sum_{k \in S} v_k$.

Input Format

The first line contains an integer $c$, indicating the subtask ID of this test point. The samples satisfy $c = 0$.

The second line contains two integers $n, m$.

The next $n$ lines: the $i$-th line contains four integers $x_i, y_i, l_i, r_i$.

The next line contains $n$ integers $v_1, \dots, v_n$.

The next $m$ lines: the $i$-th line contains three integers $A_i, B_i, C_i$.

Output Format

For each query, output one line containing one integer, representing the answer.

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

Hint

Sample 1 Explanation

For the $1$-st query, only the $3$-rd "fish" and the $5$-th "fish" satisfy the condition. Their weight intervals are $[3, 5]$ and $[1, 5]$, so $S = \{1, 2, 3, 4, 5\}$. The answer is $v_1 + v_2 + v_3 + v_4 + v_5 = 22881$.

For the $2$-nd query, only the $2$-nd "fish" and the $3$-rd "fish" satisfy the condition. Their weight intervals are $[1, 1]$ and $[3, 5]$, so $S = \{1, 3, 4, 5\}$. The answer is $v_1 + v_3 + v_4 + v_5 = 18926$.

Constraints

For all testdata:

• $1 \le n \le 5 \cdot 10^4$, $1 \le m \le 5 \cdot 10^5$.
• For all $1 \le i \le n$: $-10^6 \le x_i, y_i \le 10^6$, $1 \le l_i \le r_i \le n$.
• For all $1 \le i \le n$: $1 \le v_i \le 10^4$.
• For all $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 \le 10^9$.

For testdata other than Subtask 2, it is guaranteed that the $x, y$ coordinates of the $n$ "fish" are independently and uniformly randomly chosen within some preset ranges. Also, for the $i$-th "fish", $l_i, r_i$ and $x_i, y_i$ are independently randomly chosen, but the distribution of $l_i, r_i$ has no special restriction.

This problem uses bundled evaluation.

• Subtask 1 (10 points): $n, m \le 10^3$.
• Subtask 2 (18 points): For all $1 \le i \le n$, it is guaranteed that $\max(|x_i|, |y_i|) = 10^6$.
• Subtask 3 (18 points): For all $1 \le i \le m$, it is guaranteed that $|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): No special restrictions.

Translated by ChatGPT 5