Weighted rectangle color count.
Given a 2D plane with $n$ points, where each point has coordinates $(i, p_i)$ and a weight $a_i$.
Given an array $b$ of length $n$, with indices from $1$ to $n$.
There are $m$ queries. Each query provides a rectangle defined by $l_1, r_1, l_2, r_2$. Let the set $S = \{a_i \mid l_1 \le i \le r_1 \land l_2 \le p_i \le r_2\}$. Calculate the sum of $b_j$ for all distinct elements $j \in S$.
Input
The first line contains an integer $n$.
The next line contains $n$ integers, where the $i$-th number represents $p_i$.
The next line contains $n$ integers, where the $i$-th number represents $a_i$.
The next line contains $n$ integers, where the $i$-th number represents $b_i$.
The next line contains an integer $m$.
The next $m$ lines each contain $4$ integers representing $l_1, r_1, l_2, r_2$ for each query.
Output
For each query, output a single integer on a new line representing the answer, modulo $2^{32}$.
Examples
Input 1
9
9 8 7 6 2 4 5 3 1
1 1 4 5 1 4 1 9 1
9 1 1 4 5 1 4 1 9
9
4 9 3 6
2 9 1 8
3 8 2 4
3 9 2 7
2 8 1 6
1 9 1 9
1 3 5 7
2 3 3 3
6 6 6 6Output 1
27
27
22
27
27
27
4
0
0Note 1
For the query with answer $27$, $S=\{1,4,5,9\}$, corresponding to $b_j=9,4,5,9$, with a sum of $27$.
For the query with answer $22$, $S=\{1,4,9\}$, corresponding to $b_j=9,4,9$, with a sum of $22$.
For the query with answer $4$, $S=\{4\}$, corresponding to $b_j=4$, with a sum of $4$.
For the query with answer $0$, $S=\emptyset$, with a sum of $0$.
Subtasks
Idea: nzhtl1477, Solution: ccz181078, Code: ccz181078, Data: ccz181078
Constraints
The specific limits for each test case are shown in the table below:
| Test Case ID | $n \le$ | $m \le$ | Special Constraint |
|---|---|---|---|
| $1$ | $10$ | $10$ | None |
| $2$ | $5\times 10^3$ | $5\times 10^3$ | None |
| $3$ | $2.5\times 10^4$ | $5\times 10^4$ | $\text{A}$ |
| $4$ | $5\times 10^4$ | $10^5$ | $\text{A}$ |
| $5$ | $7.5\times 10^4$ | $1.5\times 10^5$ | $\text{A}$ |
| $6$ | $10^5$ | $2\times 10^5$ | $\text{A}$ |
| $7$ | $2\times 10^4$ | $2\times 10^4$ | None |
| $8$ | $3\times 10^4$ | $6\times 10^4$ | None |
| $9$ | $4\times 10^4$ | $8\times 10^4$ | None |
| $10$ | $5\times 10^4$ | $10^5$ | None |
| $11$ | $6\times 10^4$ | $1.2\times 10^5$ | None |
| $12$ | $7\times 10^4$ | $1.4\times 10^5$ | None |
| $13\sim 15$ | $10^5$ | $2\times 10^5$ | $\text{C}$ |
| $16\sim 18$ | $10^5$ | $2\times 10^5$ | None |
| $19$ | $10^5$ | $3\times 10^5$ | None |
| $20$ | $10^5$ | $4\times 10^5$ | None |
| $21$ | $10^5$ | $5\times 10^5$ | None |
| $22$ | $10^5$ | $6\times 10^5$ | None |
| $23$ | $10^5$ | $8\times 10^5$ | None |
| $24$ | $10^5$ | $10^6$ | None |
| $25$ | $10^5$ | $10^6$ | None |
For convenience, we denote $(a, b) \leq (c, d)$ if two points $(a, b)$ and $(c, d)$ on the plane satisfy $a \leq c$ and $b \leq d$.
Special Constraint A: For all queries, $l_2 = 1$ and $r_2 = n$.
Special Constraint C: There are at most $50$ pairs $(i, j)$ with $1 \leq i < j \leq n$ that do not satisfy $(i, p_i) \leq (j, p_j)$.
For all test cases: $2 \leq n \leq 10^5$, $1 \leq m \leq 10^6$, $1 \leq l_1\le r_1 \leq n$, $1 \leq l_2\le r_2 \leq n$. It is guaranteed that $p_i$ is a permutation and $1\le p_i, a_i, b_i \le n$.