题目背景

代号为"S-Q"科技探索计划的成功实现使得小 Soup 和罗司机进入了一个虚拟的 $k$ 维空间中，它们准备对这个 $k$ 维空间进行一番创造。

题目描述

小 Soup 和罗司机给了你 $n$ 个操作。
操作$1$：小 Soup 向 $k$ 维空间中加入一个正 $k$ 维超立方体。
操作$2$：罗司机给出一个正 $k$ 维超立方体，求当前已存在的超立方体与这个正 $k$ 维超立方体的体积交，然后输出答案 $\text{mod}\ 1919810\$的值。

输入格式

第一行两个数，$n,k$，含义已解释。
第$2\sim n+1$ 行，每行 $k+2$ 个数，第一个数代表操作编号，接下来 $k$ 个数代表这个正 $k$ 维超立方体的中心点在 $k$ 维坐标系中的坐标，最后一个数代表这个中心点与每个 $k-1$ 维超平面的距离（它们都是相等的）。

输出格式

对于每一个操作$2$，输出一个数。

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

提示

样例1解释：
如图，橙色框为两个加入的正方形，绿色框为询问，绿色块为答案。

样例3解释：

如图（红色标出部分为询问2答案）（两个解释不是同一个人造的）：

数据范围

$\begin{array}{|c|c|c|}数据编号&n&k\\1&500&1\\2\sim3&500&2\\4\sim6&500&3\\7\sim10&500&\le6\end{array}$
输入输出的数在 $\text{long long}$ 范围内，保证数据随机（正k维超立方体较分散）。