Problem Description

Counting colors in rectangles, with weights.

You are given a 2D plane with $n$ points. The $i$-th point has coordinates $(i, p_i)$ and a weight $a_i$.

You are given an array $b$ of length $n$, indexed from $1$ to $n$.

There are $m$ queries. Each query gives a rectangle $l_1, r_1, l_2, r_2$. Define the set $S = \{ a_i \mid l_1 \le i \le r_1 \land l_2 \le p_i \le r_2 \}$. For all elements $j$ in the set $S$, compute the sum of $b_j$.

Input Format

The first line contains an integer $n$.

The next line contains $n$ numbers, where the $i$-th number denotes $p_i$.

The next line contains $n$ numbers, where the $i$-th number denotes $a_i$.

The next line contains $n$ numbers, where the $i$-th number denotes $b_i$.

The next line contains an integer $m$.

The next $m$ lines each contain $4$ numbers $l_1, r_1, l_2, r_2$, describing one query.

Output Format

For each query, output one line containing an integer, which is the answer. Output the answer modulo $2^{32}$.

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 6

27
27
22
27
27
27
4
0
0

Hint

Idea: nzhtl1477, Solution: ccz181078, Code: ccz181078, Data: ccz181078.

Sample Explanation

For the query whose answer is $27$, $S = \{1,4,5,9\}$, the corresponding $b_j = 9,4,5,9$, and the sum is $27$.

For the query whose answer is $22$, $S = \{1,4,9\}$, the corresponding $b_j = 9,4,9$, and the sum is $22$.

For the query whose answer is $4$, $S = \{4\}$, the corresponding $b_j = 4$, and the sum is $4$.

For the query whose answer is $0$, $S = \emptyset$, and the sum is $0$.

Constraints

The specific limits for each test point are shown in the table below:

For convenience, we write $(a, b) \leq (c, d)$ to mean that 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 B: This special constraint is too easy to exploit for weak testdata, so it is removed.

Special constraint C: At most $50$ pairs $(i, j)$ $(1 \leq i < j \leq n)$ do not satisfy $(i, p_i) \leq (j, p_j)$.

For all test points: $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$.

Translated by ChatGPT 5