Description

You are given $n$ points in a 3D space. Each point has coordinates $X, Y, Z$, and weights $a, b$, where $b$ is initially $0$.

There are $m$ operations:

x y z w: Compute the sum of $b_i$ over all points $i$ such that $X_i\le x, Y_i\le y, Z_i\le z$. After finishing the sum, for all points $i$ such that $X_i\le x, Y_i\le y, Z_i\le z$, increase their weight $b$ by $a_i\times w$.

Input Format

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

Then $n$ lines follow, each containing four integers $X, Y, Z, a$, with meanings as described above.

Then $m$ lines follow, each containing four integers $x, y, z, w$, with meanings as described above.

Output Format

For each operation, output one line with one number representing the answer.

Since the answer may be very large, you only need to output the result modulo $2^{64}$.

10 10
5 8 4 10
6 9 6 1
1 2 7 4
7 7 3 4
9 1 5 5
3 4 8 10
8 6 1 3
2 10 2 3
4 5 9 2
10 3 10 4
9 4 2 9
10 10 4 0
3 6 1 0
2 9 4 0
4 9 4 0
7 6 8 3
4 4 7 0
3 4 9 0
7 2 9 8
7 10 2 0

0
0
0
0
0
0
12
42
12
0

Hint

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

For $100\%$ of the testdata, $1\le n,m\le 5\times 10^5$. The initial set of points and weights are generated uniformly at random. $X, Y, Z$ are permutations of $1$ to $n$. $0\le a,w\le n$. Operations are generated uniformly at random, and in each operation, with probability $0.8$, its $w$ is $0$.

This problem is scored based on the number of queries your program answers correctly. If your program answers the first $x$ queries correctly, then if $2x\le m$, you will get a score of $\lfloor\frac{100x}{m}\rfloor\%$. Otherwise, you will get $\lfloor50+50\times(\frac{2x-m}{m})^2\rfloor\%$. The spj will stop reading when it reads the first wrong answer, or reaches the end of your output, or reads the first $m$ lines. Any further output will be ignored. Do not add spaces at the end of lines.

Note: If your program TLEs, you will get 0 points.

Translated by ChatGPT 5