Given $n$ points in three-dimensional 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: Calculate the sum of $b_i$ for all $i$ such that $X_i \le x, Y_i \le y, Z_i \le z$. After calculating the sum, for all points $i$ such that $X_i \le x, Y_i \le y, Z_i \le z$, add $a_i \times w$ to their weight $b$.

Input

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

The next $n$ lines each contain four integers $X, Y, Z, a$, as described above.

The next $m$ lines each contain four integers $x, y, z, w$, as described above.

Output

For each operation, output one integer representing the answer.

Since the answer can be very large, output the result modulo $2^{64}$.

Examples

Input 1

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

Output 1

0
0
0
0
0
0
12
42
12
0

Subtasks

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

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

The score for this problem is based on the number of queries your program answers correctly. If your program correctly answers the first $x$ queries, and $2x \le m$, you will receive $\lfloor\frac{100x}{m}\rfloor\%$ of the points; otherwise, you will receive $\lfloor50+50\times(\frac{2x-m}{m})^2\rfloor\%$ of the points. The spj will stop reading upon encountering the first incorrect answer, reaching the end of the output, or after reading the first $m$ lines; subsequent information will be ignored. Please do not add trailing spaces at the end of lines.

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