题目背景

像是各种名著啦，励志小说之类的，不全都是人类为人类而写的文字吗？为了社会发展，为了鼓励人类。但这样也势必会引发一些人的反感。

问题描述

铃很讨厌这些文字，于是她决定创建一些自己的文字。一个整数序列 $a$ 是优美的，当且仅当 $\forall i, 0 \le a _ i < k$ 且 $a _ {i + 1} \equiv a _ i + 1 \pmod k$，其中 $k$ 是一个常数。容易发现这样的序列可以用首项和长度两个非负整数来表示。

铃有 $n$ 个优美的序列，她可以将每个序列分成至多三个连续子段。随后铃可以选择一部分子段，将选择的子段按任意顺序拼接，使得最后拼接出来的序列仍然是优美的。铃想使最后拼接出来的序列尽量长，但她并不会这个题，于是来问你了。

输入格式

第一行两个整数 $n, k$，表示初始序列个数和题目描述中的常数。

接下来 $n$ 行，每行两个整数 $c _ i$ 和 $l _ i$，表示第 $i$ 个序列的首项和长度。

输出格式

第一行两个整数 $C, L$（$0\le C < k$），表示最后序列的首项和能达到的最大长度。

接下来 $n$ 行，第 $i$ 行有 $2 \sim 4$ 个整数：

• 第一个整数 $m$（$1 \le m \le 3$）表示将第 $i$ 个序列划分成了多少个子段。
• 接下来 $m$ 个 正整数 表示每个子段的长度是多少。你需要保证这些数加起来等于 $l _ i$。

最后一行，第一个整数 $s$ 表示最后序列是由 $s$ 段拼起来的。接下来 $s$ 个正整数表示每一段的长度。你需要保证这些子段在之前描述划分时都出现过。

样例 1 输入

5 5
2 1
0 5
1 2
4 2
0 3

样例 1 输出

4 9
1 1 
2 3 2 
1 2 
1 2 
1 3 
4 2 2 2 3 

样例 1 解释

原序列是 $\{2\}, \{0, 1, 2, 3, 4\}, \{1, 2\}, \{4, 0\}, \{0, 1, 2\}$，拆分为 $\{2\}, \{0, 1, 2\}, \{3, 4\}, \{1, 2\}, \{4, 0\}, \{0, 1, 2\}$，最后拼成 $\{4, 0, 1, 2, 3, 4, 0, 1, 2\}$。

样例 2 输入 / 输出

见下发文件 people2.in/ans，该样例满足特殊性质 BC，$n, k \le 100000$。

样例 3 输入 / 输出

见下发文件 people3.in/ans，该样例满足特殊性质 C，$n, k \le 100000$。

样例 4 输入 / 输出

见下发文件 people4.in/ans，该样例满足特殊性质 BD，$n, k \le 500$。

样例 5 输入 / 输出

见下发文件 people5.in/ans，该样例满足特殊性质 B，$n, k \le 100000$。

样例 6 输入 / 输出

见下发文件 people6.in/ans，该样例满足特殊性质 A，$n, k \le 100000$。

评测用例规模与约定

如果你的输出的最终序列长度和答案相同，并且输出格式正确（仍输出了那么多在应该的范围内的整数），那么你至少可以获得这个测试点 $20\%$ 的分数。如果构造正确，则可以获得这个测试点的满分。

共 $20$ 个测试点，每个 $5$ 分。具体数据范围见下。

测试点编号	$n\le$	$k$	特殊性质
$1 \sim 3$	$5$	$\le 5$	$l _ i \le 5$，A
$4$	$10$	$= 3$	$l _ i \le 100$，B
$5$			A
$6 \sim 8$	$10 ^ 5$	$\le 10 ^ 5$	C
$9 \sim 10$	$500$	$\le 500$	BD
$11$	$10 ^ 5$	$\le 10 ^ 5$
$12 \sim 14$			B
$15 \sim 16$	$100$	$= 10 ^ 5$	A
$17 \sim 19$	$10 ^ 5$	$= 10$
$20$		$\le 10 ^ 5$	无

特殊性质 A：先确定 $n, k$， 之后 $c _ i, l _ i$ 均在可能的范围内均匀随机。

特殊性质 B：最终序列长度等于所有序列长度之和（即每个元素都能被使用上）。

特殊性质 C：最终序列长度在模 $k$ 意义下为 $0$。

特殊性质 D：存在一组最优解，使得其不需要拆分原本的 $n$ 个序列。

对于全部数据，有 $1 \le n \le 10 ^ 5$，$3 \le k \le 10 ^ 5$，$0 \le c _ i < k$，$1 \le l _ i \le 10 ^ 9$。

本题下发 checker，见下发文件 checker.cpp，你无需关注其中内容。你可以使用 g++ checker.cpp -o checker -std=c++17 来编译 checker，使用 ./checker <input-file> <output-file> <answer-file> 来测试你的答案，checker 会输出你的得分。如果输入文件不合法，checker 会报错。