P7104 "C.E.L.U-01" Beyond Dimensions

The successful implementation of the tech exploration plan codenamed "S-Q" has enabled Little Soup and Luo Si Ji to enter a virtual $k$-dimensional space. They are ready to create something in this $k$-dimensional space.

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\ $.

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).

For each operation $2$, output one number.

**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