Description

Little Soup and Luo Si Ji give you $n$ operations.
Operation $1$: Little Soup adds a regular (axis-aligned) $k$-dimensional hypercube into the $k$-dimensional space.
Operation $2$: Luo Si Ji gives a regular (axis-aligned) $k$-dimensional hypercube. Compute the volume of the intersection between the currently existing hypercubes and this hypercube, then output the value $\text{mod}\ 1919810\$.

Input Format

The first line contains two integers $n, k$, as explained above.
Lines $2$ to $n+1$ each contain $k+2$ numbers. The first number is the operation type. The next $k$ numbers are the coordinates of the center of the regular $k$-dimensional hypercube in the $k$-dimensional coordinate system. The last number is the distance from this center to each $(k-1)$-dimensional hyperplane (they are all equal).

Output Format

For each operation $2$, output one number.

3 2
1 1 1 1
1 2 2 1
2 1 2 1

3

5 3
1 0 0 0 3
1 1 -1 0 1
2 0 0 0 2
1 19 3 5 6
2 1 0 0 30

64
1944

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

9
45
0
0

Hint

Explanation for Sample 1:
As shown in the figure, the orange boxes are the two added squares, the green box is the query, and the green area is the answer.

Explanation for Sample 3:

As shown in the figure (the red marked part is the answer for Query 2) (the two explanations were not made by the same person):

Constraints

$\begin{array}{|c|c|c|}\text{Testdata ID}&n&k\\1&500&1\\2\sim3&500&2\\4\sim6&500&3\\7\sim10&500&\le6\end{array}$
The input and output numbers are within the $\text{long long}$ range. The testdata is guaranteed to be random (the regular $k$-dimensional hypercubes are relatively scattered).

Translated by ChatGPT 5