H-同源数组(Hard Version)

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
Special Judge, 64bit IO Format: %lld

题目描述

本题有Easy,Hard两个版本，两个版本之间的区别仅在数据范围，通过Hard Version的代码可以直接通过Easy Version。保证Easy Version的测试用例集是Hard Version的子集

智乃酱最近学习了前缀和、差分。她现在对于这两个操作产生了浓厚的兴趣。

具体来说，前缀和是这样一种操作，假设 ${s}$ 数组是 ${a}$ 数组的前缀和数组，则有
$\left\{\begin{matrix}s_0=a_0\; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \\ s_i=a_{i}+s_{i-1}(i \geq 1)\end{matrix}\right.$
而差分的操作则是前缀和反过来，假设 ${d}$ 数组是 ${a}$ 数组的差分数组，则有
$\left\{\begin{matrix}d_0=a_0\; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \, \\ d_i=a_{i}-a_{i-1}(i \geq 1)\end{matrix}\right.$
我们将先求出 ${s}$ 数组，再把 ${s}$ 中的值赋值回 ${a}$ 称为对 ${a}$ 数组做一次前缀和，同理，将先求出 ${d}$ 数组，再把 ${d}$ 中的值赋值回 ${a}$ 数组称之为一次差分。

如果两个长度相同的数组 ${a,b}$ 可以通过对数组 ${a}$ 或者数组 ${b}$ 做若干次前缀和或者差分，使两个数组中所有元素在mod ${p}$ (p是一个素数)下是相等的，则称两个数组同源。
显然易得，如果存在三个长度相同的数组 ${a,b,c}$ ，如果 ${a,b}$ 同源且 ${b,c}$ 同源，则 ${a,c}$ 也是同源的。

我们把一些两两之间互相同源的数组放到一起，它们就称为一个“同源集合”。

现在给你n个长度大小均为m的数组，你需要将它们划分成若干个同源集合，要求你划分的集合数目最少。
请输出一个合理的划分方案。

输入描述:

第一行输入三个正整数 $n,m,p(1 \leq n \leq 100,1 \leq m \leq 10^3, 2 \leq p \leq 10^9+7)$ 并且保证p是一个质数。
接下来n行，每行m个整数 $a_{ij}(0 \leq a_{ij} <p)$ 表示第i个数组的第j个元素

输出描述:

本题为spj，你可以输出任何符合题目要求的答案。
首先输出一个正整数g表示划分的同源集合数目。
接下来按照顺序输出每个集合中的数组编号。（数组从0开始编号）
输出行，首先输出一个整数，表示集合的大小，接下来输出一行若干整数，整数与整数之间空一个空格。

示例1

输入

复制

15 5 998244353
0 0 0 0 5
1 1 1 1 1
0 0 1 1 1
1 3 6 10 15
0 0 0 7 7
1 0 0 0 0
0 0 0 0 6
0 0 0 7 10
0 0 0 9 8
1 2 1 2 1
0 0 0 0 5
0 0 1 2 1
1 2 3 4 5
0 0 0 9 2
0 0 0 7 10086

输出

复制

示例2

输入

复制

6 8 7
4 4 6 4 0 2 1 1
4 2 0 2 1 6 4 1
4 5 5 2 6 5 5 4
4 4 6 4 0 2 1 1
4 5 5 2 6 5 5 1
4 2 0 2 1 6 4 1

输出

复制

1
6
0 1 2 3 4 5