考古学家在 Cycleland 金字塔之一的地牢中发现了一个秘密通道。要进入金库,他们必须打开门上一把不寻常的锁。锁由n个单词组成,每个单词由一些象形文字组成。锁附近的墙上有一个圆形开关。该开关的每次旋转都会根据某些规则改变象形文字。附近的说明说,只有当锁上写的单词按字典顺序排序时,门才会打开(字典比较的定义在注释部分给出)。
更改象形文字的规则如下。圆形开关顺时针旋转一圈,将每个象形文字替换为字母表中的下一个象形文字,即,象形文字 x (1 ≤ x ≤ c - 1) 替换为象形文字 (x + 1),象形文字 c 替换为象形文字 1。
帮助考古学家确定他们应该顺时针旋转多少次才能打开门,或者确定这是不可能的,即字母表的循环移位不会使单词序列按字典顺序排序。
输入
输入的第一行包含两个整数 n 和 c (2 ≤ n ≤ 500 000, 1 ≤ c ≤ 106) — 写在锁上的单词数以及不同象形文字的数量。
接下来的 n 行每一行都包含一个单词的描述。其中第 i 行以整数 li (1 ≤ li ≤ 500 000) 开头,表示第 i 个单词的长度,后跟 li 整数 wi, 1, wi, 2, ..., wi, li (1 ≤ wi, j ≤ c) – 组成第 i 个单词的象形文字的索引。索引为 1 的象形文字是字母表中最小的,索引为 c 的象形文字是最大的。
保证所有单词的总长度不超过106。
输出
如果可以通过旋转圆形开关来打开门,请打印整数 x (0 ≤ x ≤ c - 1),它定义了所需的顺时针旋转次数。如果有多个有效的 x,则打印其中任何一个。
如果用这种方法无法开门,则打印 - 1。
示例
输入 #1
4 3 2 3 2 1 1 3 2 3 1 4 2 3 1 2
输出 #1
1
输入 #2
2 5 2 4 2 2 4 2
输出 #2
0
输入 #3
4 4 1 2 1 3 1 4 1 2
输出 #3
-1
注意
如果以下两个条件之一成立,则长度为 m 的单词 a1, a2, ..., am 按字典顺序不大于长度为 k 的单词 b1, b2, ..., bk:
- 在第一个位置 i,使得 ai ≠ bi,字符 ai 在字母表中比字符 bi 更早,即 a 在它们不同的第一个位置具有较小的字符;
- 如果没有这样的位置 i 并且 m ≤ k,即第一个单词是第二个单词的前缀或者两个单词相等。
如果每个单词(最后一个除外)按字典顺序不大于下一个单词,则称单词序列按字典顺序排序。
在第一个示例中,将圆形开关顺时针旋转 1 个位置后,文字如下所示:
在第二个示例中,单词已按字典顺序排序。
在最后一个示例中,可以检查字母表的转换是否有效。