Ultimate AVX2 Hardware Instruction Speedup

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

There are $m$ queries, each providing $A_i, B_i, C_i$. Define $f(k, A_i, B_i, C_i) = 1$ if and only if $A_ix_k + B_iy_k + C_i < 0$, otherwise $f(k, A_i, B_i, C_i) = 0$. Let $S$ be the set of all integers contained in the union of intervals $[l_k, r_k]$ for all $k$ such that $f(k, A_i, B_i, C_i) = 1$. Calculate $\sum_{k \in S} v_k$.

Input

The first line contains an integer $c$, representing the subtask number this test case belongs to. The sample satisfies $c=0$.

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

The next $n$ lines each contain 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 each contain three integers $A_i, B_i, C_i$.

Output

For each query, output a single line containing an integer representing the answer.

Examples

Input 1

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

Output 1

22881
18926

Note 1

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

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

Constraints

For all test cases:

• $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 test cases other than Subtask 2, it is guaranteed that the $x, y$ coordinates of the $n$ fishes are chosen uniformly at random within certain preset ranges; furthermore, for the $i$-th fish, $l_i, r_i$ and $x_i, y_i$ are chosen independently at random, though there are no special restrictions on the distribution of $l_i, r_i$.

This problem uses bundled testing.

• 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.