CF731D.80-th Level Archeology

Archeologists have found a secret pass in the dungeon of one of the pyramids of Cycleland. To enter the treasury they have to open an unusual lock on the door. The lock consists of n words, each consisting of some hieroglyphs. The wall near the lock has a round switch. Each rotation of this switch changes the hieroglyphs according to some rules. The instruction nearby says that the door will open only if words written on the lock would be sorted in lexicographical order (the definition of lexicographical comparison in given in notes section).

The rule that changes hieroglyphs is the following. One clockwise rotation of the round switch replaces each hieroglyph with the next hieroglyph in alphabet, i.e. hieroglyph x (1 ≤ x ≤ c - 1) is replaced with hieroglyph (x + 1), and hieroglyph c is replaced with hieroglyph 1.

Help archeologist determine, how many clockwise rotations they should perform in order to open the door, or determine that this is impossible, i.e. no cyclic shift of the alphabet will make the sequence of words sorted lexicographically.

考古学家在Cycleland某座金字塔的地牢中发现了一条秘密通道。为了进入宝库，他们必须打开门上一种不寻常的锁。该锁由 $n$ 个单词组成，每个单词均由若干象形文字构成。锁旁的墙壁上装有一个圆形旋钮。每次旋转该旋钮，都会根据特定规则改变所有象形文字。旁边说明写道：仅当锁上显示的单词按字典序排列时，门才会开启（字典序比较的定义见“注释”部分）。

改变象形文字的规则如下：顺时针旋转一次该圆形旋钮，会将每个象形文字替换为字母表中的下一个象形文字，即象形文字 $x$（其中 $1 \le x \le c - 1$）被替换为象形文字 $(x + 1)$，而象形文字 $c$ 则被替换为象形文字 $1$。

请帮助考古学家确定：为打开这扇门，他们需要顺时针旋转多少次？或者判断这是不可能的——即不存在某个字母表的循环移位，使得单词序列满足字典序排列。

The first line of the input contains two integers n and c (2 ≤ n ≤ 500 000, 1 ≤ c ≤ 106) — the number of words, written on the lock, and the number of different hieroglyphs.

Each of the following n lines contains the description of one word. The i-th of these lines starts with integer l__i (1 ≤ l__i ≤ 500 000), that denotes the length of the i-th word, followed by l__i integers w__i, 1, w__i, 2, ..., w__i, l__i (1 ≤ w__i, j ≤ c) — the indices of hieroglyphs that make up the i-th word. Hieroglyph with index 1 is the smallest in the alphabet and with index c — the biggest.

It's guaranteed, that the total length of all words doesn't exceed 106.

输入的第一行包含两个整数 $n$ 和 $c$（$2 \leq n \leq 500\,000$，$1 \leq c \leq 10^6$）——分别表示锁上所写单词的个数以及不同象形文字的种类数。

接下来的 $n$ 行中，每行描述一个单词。其中第 $i$ 行首先是一个整数 $l_i$（$1 \leq l_i \leq 500\,000$），表示第 $i$ 个单词的长度；随后是 $l_i$ 个整数 $w_{i,1},\, w_{i,2},\, \dots,\, w_{i,l_i}$（$1 \leq w_{i,j} \leq c$），表示构成第 $i$ 个单词的各个象形文字的编号。编号为 $1$ 的象形文字在字母表中最小，编号为 $c$ 的象形文字最大。

保证所有单词的总长度不超过 $10^6$。

If it is possible to open the door by rotating the round switch, print integer x (0 ≤ x ≤ c - 1) that defines the required number of clockwise rotations. If there are several valid x, print any of them.

If it is impossible to open the door by this method, print  - 1.

如果可以通过旋转圆形开关来打开门，则输出整数 $x$（$0 \le x \le c - 1$），表示所需的顺时针旋转次数。若存在多个合法的 $x$，输出任意一个即可。

如果无法通过该方法打开门，则输出 $-1$。

Word _a_1, _a_2, ..., a__m of length m is lexicographically not greater than word _b_1, _b_2, ..., b__k of length k, if one of two conditions hold:

• at first position i, such that a__i ≠ b__i, the character a__i goes earlier in the alphabet than character b__i, i.e. a has smaller character in the first position where they differ;
• if there is no such position i and m ≤ k, i.e. the first word is a prefix of the second or two words are equal.

The sequence of words is said to be sorted in lexicographical order if each word (except the last one) is lexicographically not greater than the next word.

In the first sample, after the round switch is rotated 1 position clockwise the words look as follows:

1 3
2
3 1 2
3 1 2 3

In the second sample, words are already sorted in lexicographical order.

In the last sample, one can check that no shift of the alphabet will work.

长度为 $m$ 的单词 $a_1,\,a_2,\,\dots,\,a_m$ 在字典序上不大于长度为 $k$ 的单词 $b_1,\,b_2,\,\dots,\,b_k$，当且仅当满足以下两个条件之一：

• 在首个满足 $a_i \ne b_i$ 的位置 $i$ 上，字符 $a_i$ 在字母表中位于字符 $b_i$ 之前，即：两单词在第一个不同的位置上，前者的字符更小；
• 不存在这样的位置 $i$，且 $m \le k$，即第一个单词是第二个单词的前缀，或两个单词完全相等。

若序列中每个单词（除最后一个外）在字典序上都不大于其后一个单词，则称该单词序列按字典序排序。

在第一个样例中，将轮盘顺时针旋转 1 个位置后，各单词变为如下形式：

1 3
2
3 1 2
3 1 2 3

在第二个样例中，单词已按字典序排序。

在最后一个样例中，可以验证：无论对字母表作何种平移（循环移位），均无法使单词序列满足字典序。