# 超时空军团

- 参考时间限制：0.5 秒（参考环境：[评测环境与性能](../../../docs/评测环境与性能.md)；仅供预估）
- 实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 2 倍，按 0.5 秒的倍数向上取整；若平台仅支持更粗的粒度，再向上取整到平台可设置值。
- 内存限制：256 MB

## 背景故事

一名超时空军团兵潜入游戏中的苏军基地，准备切断建筑之间的通信链路。但只要有两座建筑无法相互通信，警报就会响起。

他打算在始终保持通信畅通的前提下，破坏尽可能多的链路。指挥官还想知道，一共有多少种不同的行动顺序。

## 形式化问题描述

基地位于 $N$ 行、$M$ 列的网格内，有 $K$ 座带编号的建筑。建筑 $i$ 位于 $(X_i,Y_i)$ ，建造时间为 $T_i$ .建造时间互不相同，但不同建筑可以占据同一格，计数时仍视为不同建筑。

以建筑 $i$ 为中心、非负整数 $r$ 为半径的范围，包含所有满足

$$\max(|X_j-X_i|,|Y_j-Y_i|)\le r$$

的建筑 $j$ .范围包含中心建筑自身；半径可以为 $0$ ，此时包括同一坐标上的所有建筑。

建筑 $i$ 有 $P_i$ 个阈值 $D_{i1},\ldots,D_{iP_i}$ .对每个阈值 $D$ ，按以下方式生成链路：

1. 找到包含至少 $D$ 座建筑的最小半径，计数包含建筑 $i$ .
2. 在该半径包含的全部建筑中，选择建造时间最大的建筑 $j$ .若边界上有多座建筑，全部参与选择，不只取排序中的前 $D$ 座。
3. 若 $j\ne i$ ，在 $i,j$ 之间加入一条无向链路；若 $j=i$ ，不添加链路。

阈值可以重复。无论同一对建筑被选择多少次，最终都只有一条链路。保证最终的无向图连通。

每次行动删除一条当前存在的链路，要求每次删除后图仍然连通。求删除条数达到最大值的行动序列数量，对输入整数 $\mathrm{mod}$ 取模。两序列只要某一步删除的链路不同，就算不同方案；空序列计为一种方案。

## 输入格式

第一行包含四个整数 $N,M,K,\mathrm{mod}$ .

接下来 $K$ 行，第 $i$ 行先给出 $X_i,Y_i,T_i,P_i$ ，再给出 $P_i$ 个整数 $D_{i1},\ldots,D_{iP_i}$ .

## 输出格式

输出一行一个整数，表示方案数对 $\mathrm{mod}$ 取模的结果。

## 样例 1

### 输入

```text
1 5 3 10
1 1 5 1 2
1 5 1 1 2
1 3 10 1 3
```

### 输出

```text
1
```

### 解释

前两座建筑分别与第三座相连，得到一棵树。不能再删除任何链路，只有空序列一种方案。

## 样例 2

### 输入

```text
1 4 3 12
1 1 1 2 2 3
1 2 2 1 3
1 4 3 1 3
```

### 输出

```text
3
```

### 解释

三座建筑两两相连。最多删除一条链路，三条链路都可以选择。

## 样例 3

### 输入

```text
1 2 3 1000000007
1 1 1 2 1 3
1 1 2 1 3
1 2 3 1 3
```

### 输出

```text
3
```

### 解释

第一座建筑的阈值 $1$ 对应半径 $0$ ，范围内同时有第一、第二座建筑，故连接第二座。其余阈值还生成到第三座的链路，最终得到三角形。

## 样例 4

### 输入

```text
1 1 1 2
1 1 0 1 1
```

### 输出

```text
1
```

### 解释

唯一建筑不会和自己相连，空序列是唯一方案。


## 数据范围与保证

- $1\le N,M$ ，$NM\le10^6$ ，$1\le K\le200$ .
- $1\le X_i\le N$ ，$1\le Y_i\le M$ ，$0\le T_i\le10^{18}$ ；所有 $T_i$ 互不相同。
- $1\le P_i\le K$ ，$1\le D_{ij}\le K$ ；阈值可以重复。
- $2\le\mathrm{mod}\le1000000500$ ，不保证为质数。
- 所有输入量均为整数，生成的链路图保证连通。$K=1$ 时也视为连通。

### 数据分组

| 分值比例 | 额外条件 |
| --- | --- |
| 30% | $N,M\le100$ ，$K\le8$ ，$T_i\le200$ ，$\mathrm{mod}$ 为质数 |
| 30% | $N,M\le1000$ ，$\mathrm{mod}$ 为质数 |
| 10% | $\min(N,M)=1$ ，$\mathrm{mod}$ 为质数 |
| 10% | $\mathrm{mod}$ 为质数 |
| 20% | 无额外条件 |