Background

The successful implementation of the "S-Q" technology exploration project has allowed Little Soup and Driver Luo to enter a virtual $k$-dimensional space, where they plan to engage in creative activities.

Problem Description

Little Soup and Driver Luo have given you $n$ operations.
Operation $1$: Little Soup adds a positive $k$-dimensional hypercube to the space.
Operation $2$: Driver Luo provides a positive $k$-dimensional hypercube, and you need to calculate the volume intersection between this hypercube and the existing ones, then output the result modulo $1919810$.

Input Format

The first line contains two numbers, $n$ and $k$, as explained.
Lines $2$ to $n+1$ each contain $k+2$ numbers. The first number indicates the operation type, the next $k$ numbers represent the coordinates of the center of the positive $k$-dimensional hypercube in the $k$-dimensional coordinate system, and the last number represents the distance from the center to each $k-1$-dimensional hyperplane (all are equal).

Output Format

For each Operation $2$, output a number.

Sample Input and Output

Sample Input #1

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

Sample Output #1

3

Sample Input #2

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

Sample Output #2

64
1944

Sample Input #3

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

Sample Output #3

9
45
0
0

Notes

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

Sample 3 Explanation:

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

Data Range

$\begin{array}{|c|c|c|} \text{Data ID} & n & k \\ 1 & 500 & 1 \\ 2\sim3 & 500 & 2 \\ 4\sim6 & 500 & 3 \\ 7\sim10 & 500 & \le 6 \end{array}$
The numbers in the input and output are within the range of long long, and the data are guaranteed to be random (the positive $k$-dimensional hypercubes are relatively dispersed).

见题面 Input 部分

见题面 Output 部分