Description

给定一个三维空间上 $n$ 个点，每个点有坐标 $X,Y,Z$，权值 $a,b$，$b$ 初始为 $0$。

有 $m$ 个操作：

x y z w：求所有 $X_i\le x,Y_i\le y,Z_i\le z$ 的 $i$ 的 $b_i$ 的和，求和结束后，将所有 $X_i\le x,Y_i\le y,Z_i\le z$ 的点 $i$，其 $b$ 权值加上 $a_i\times w$。

Input Format

第一行两个数 $n,m$。

之后 $n$ 行，每行四个数 $X,Y,Z,a$ 意义如上述。

之后 $m$ 行，每行四个数 $x,y,z,w$，意义如上述。

Output Format

对每个操作，输出一行一个数表示答案。

由于答案可能很大，所以只需要输出答案对 $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

对于 $100\%$ 的数据，满足 $1\le n,m\le 5\times 10^5$，初始点集以及权值为均匀随机生成，$X,Y,Z$ 为 $1$ 到 $n$ 的排列，$0\le a,w\le n$，操作为均匀随机生成，每次操作有 $0.8$ 的概率其 $w$ 为 $0$。

本题按照你的程序正确回答的询问个数给分，若你的程序正确回答了前 $x$ 个询问，若 $2x\le m$，你将得到 $\lfloor\frac{100x}{m}\rfloor\%$ 的分数，否则你将得到 $\lfloor50+50\times(\frac{2x-m}{m})^2\rfloor\%$ 的分数。spj 将会在读取到第一个错误的答案或读取到输出末尾或读取完前 $m$ 行时终止读取，之后的信息将被忽略，请勿在行末添加空格。

注意：若你的程序 TLE，你将会得到 0 分。