Colored Rectangle Sum

Given a 2D plane with ( n ) points where the ( i )-th point is located at ( (i, p_i) ) and has a color ( a_i ). You are also given an array ( b ) of length ( n ) (indexed from ( 1 ) to ( n )). For each query, given four integers ( l_1, r_1, l_2, r_2 ), define the set ( S = { a_i \mid l_1 \le i \le r_1 \text{ and } l_2 \le p_i \le r_2 } ). Your task is to compute the sum of ( b_j ) for each distinct color ( j ) in ( S ).

inputFormat

The input consists of the following parts:\n\n1. The first line contains two integers ( n ) and ( m ), representing the number of points and the number of queries, respectively.\n2. The second line contains ( n ) integers ( p_1, p_2, \ldots, p_n ), representing the second coordinate of each point.\n3. The third line contains ( n ) integers ( a_1, a_2, \ldots, a_n ), representing the color of each point.\n4. The fourth line contains ( n ) integers ( b_1, b_2, \ldots, b_n ), representing the value associated with each color.\n5. Each of the next ( m ) lines contains four integers ( l_1, r_1, l_2, r_2 ), describing a query.

outputFormat

For each query, output a single line containing the sum of ( b_j ) for all distinct colors ( j ) that appear in the set ( S ).

sample

5 2
2 3 1 5 4
1 2 1 3 2
10 20 30 40 50
1 3 1 3
2 5 3 5

30
50