Background

This problem is a Ynoi problem from the year 2077. In 2077, the 77-year-old grandpa Ynoi problem setter was beyond saving, and increased the Constraints by $10^{100}$ times, blocking all high-complexity algorithms.

In 2076, the Soviet Union believed it could no longer compete with the Allied forces. The last leader, Furbachog, started a war against the Allies. They imagined that, like the military exercises in the 1980s, they could first clear the way with nuclear bombs, then send an iron flood, and within a week plant red flags all over the English Channel. However, the Soviet Union’s technological progress was slow. In 2076, Soviet conscripts were still using PPSh submachine guns, and their proud Apocalypse tanks were no match for the Allies’ newly developed Prism tanks...

After losing the war, Furbachog was hung on a streetlight by the people to keep “shining” there, and soon in 2077 the red flag fell, and the once huge Soviet Union disintegrated. The stimulation of war led the Allies to develop a lot of new technologies. To deal with Soviet nuclear bombs, the Allies had been secretly developing a “chronosphere” (chaoshikong chuansong yi). They carried out many random teleportation tests using the device. In one test, a former Soviet spy suddenly shot and killed the engineer in the experiment, sacrificed himself, and teleported this problem to the year 2021. This problem is extremely important, because chronosphere teleportation is essentially a modification query on high-dimensional space. If you can understand high-dimensional space modification queries, you can achieve chronosphere teleportation!

In 2021, Soviet scientists received the news that the Soviet Union would lose in 2077 and then disintegrate. Their hearts were filled with respect for the unknown hero and fear of the future world. However, after the Soviets in 2021 decrypted the information from 2077, they found in horror that existing judging machines could not support such large-scale judging, so they could only use smaller Constraints. Everyone is welcome to consider using high-complexity algorithms to pass this problem, to help the Soviets defeat the Allies.

Problem 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