English · Original
Chinese · Translation
Formal · Original
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.
## Input
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.
## Output
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.
[samples]
## Note
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.
考古学家在Cycleland一座金字塔的地下墓穴中发现了一条秘密通道。要进入宝库，他们必须打开一扇门上的特殊锁。锁上显示着 #cf_span[n] 个词，每个词由若干象形文字组成。锁旁的墙上有一个圆形开关，每次旋转该开关都会根据特定规则改变所有象形文字。旁边说明指出，只有当锁上的词按字典序排列时，门才会打开（字典序比较的定义见注释部分）。
改变象形文字的规则如下：圆形开关顺时针旋转一次，会将每个象形文字替换为字母表中的下一个象形文字，即象形文字 #cf_span[x]（#cf_span[1 ≤ x ≤ c - 1]）被替换为象形文字 #cf_span[(x + 1)]，而象形文字 #cf_span[c] 则被替换为象形文字 #cf_span[1]。
请帮助考古学家确定，需要顺时针旋转多少次才能打开门，或者判断这是不可能的——即不存在任何字母表的循环移位能使词序列按字典序排列。
输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[c]（#cf_span[2 ≤ n ≤ 500 000]，#cf_span[1 ≤ c ≤ 106]），分别表示锁上词的数量和不同象形文字的种类数。
接下来的 #cf_span[n] 行，每行描述一个词。第 #cf_span[i] 行以整数 #cf_span[li]（#cf_span[1 ≤ li ≤ 500 000]）开头，表示第 #cf_span[i] 个词的长度，随后是 #cf_span[li] 个整数 #cf_span[wi, 1], #cf_span[wi, 2], ..., #cf_span[wi, li]（#cf_span[1 ≤ wi, j ≤ c]），表示构成该词的象形文字的编号。编号为 #cf_span[1] 的象形文字是字母表中最小的，编号为 #cf_span[c] 的是最大的。
保证所有词的总长度不超过 #cf_span[106]。
如果可以通过旋转圆形开关打开门，请输出一个整数 #cf_span[x]（#cf_span[0 ≤ x ≤ c - 1]），表示所需的顺时针旋转次数。如果有多个合法的 #cf_span[x]，输出任意一个即可。
如果通过此方法无法打开门，请输出 #cf_span[ - 1]。
长度为 #cf_span[m] 的词 #cf_span[a1, a2, ..., am] 被称为字典序不大于长度为 #cf_span[k] 的词 #cf_span[b1, b2, ..., bk]，当且仅当满足以下两个条件之一：
词序列被称为按字典序排列，当且仅当每个词（最后一个除外）都字典序不大于其后一个词。
在第一个样例中，圆形开关顺时针旋转 #cf_span[1] 次后，词变为：
在第二个样例中，词已经按字典序排列。
在最后一个样例中，可以验证无论怎样移位字母表都无法满足条件。
## Input
输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[c]（#cf_span[2 ≤ n ≤ 500 000]，#cf_span[1 ≤ c ≤ 106]），分别表示锁上词的数量和不同象形文字的种类数。接下来的 #cf_span[n] 行，每行描述一个词。第 #cf_span[i] 行以整数 #cf_span[li]（#cf_span[1 ≤ li ≤ 500 000]）开头，表示第 #cf_span[i] 个词的长度，随后是 #cf_span[li] 个整数 #cf_span[wi, 1], #cf_span[wi, 2], ..., #cf_span[wi, li]（#cf_span[1 ≤ wi, j ≤ c]），表示构成该词的象形文字的编号。编号为 #cf_span[1] 的象形文字是字母表中最小的，编号为 #cf_span[c] 的是最大的。保证所有词的总长度不超过 #cf_span[106]。
## Output
如果可以通过旋转圆形开关打开门，请输出一个整数 #cf_span[x]（#cf_span[0 ≤ x ≤ c - 1]），表示所需的顺时针旋转次数。如果有多个合法的 #cf_span[x]，输出任意一个即可。如果通过此方法无法打开门，请输出 #cf_span[ - 1]。
[samples]
## Note
长度为 #cf_span[m] 的词 #cf_span[a1, a2, ..., am] 被称为字典序不大于长度为 #cf_span[k] 的词 #cf_span[b1, b2, ..., bk]，当且仅当满足以下两个条件之一：
在第一个不同的位置 #cf_span[i]，使得 #cf_span[ai ≠ bi]，字符 #cf_span[ai] 在字母表中位于 #cf_span[bi] 之前，即在第一个不同的位置，#cf_span[a] 的字符更小；
或者不存在这样的位置 #cf_span[i]，且 #cf_span[m ≤ k]，即第一个词是第二个词的前缀，或两个词完全相等。
词序列被称为按字典序排列，当且仅当每个词（最后一个除外）都字典序不大于其后一个词。
在第一个样例中，圆形开关顺时针旋转 #cf_span[1] 次后，词变为：
1 3
2
3 1 2
3 1 2 3
在第二个样例中，词已经按字典序排列。
在最后一个样例中，可以验证无论怎样移位字母表都无法满足条件。
Let $ n $ be the number of words, $ c $ the size of the alphabet, and let each word $ w_i $ be a sequence of $ l_i $ integers from $ [1, c] $.
Define a cyclic shift $ r \in \{0, 1, \dots, c-1\} $ as a transformation where each hieroglyph $ x $ is mapped to $ (x + r - 1) \bmod c + 1 $.
Let $ w_i^{(r)} $ denote the word $ w_i $ after applying shift $ r $.
We say the sequence $ w_1^{(r)}, w_2^{(r)}, \dots, w_n^{(r)} $ is lexicographically sorted if for all $ i \in [1, n-1] $, $ w_i^{(r)} \leq_{\text{lex}} w_{i+1}^{(r)} $.
We are to find any $ r \in \{0, 1, \dots, c-1\} $ such that the sequence $ w_1^{(r)}, \dots, w_n^{(r)} $ is lexicographically sorted. If no such $ r $ exists, return $ -1 $.
---
**Formal Problem Statement:**
Given:
- Integers $ n, c $ with $ 2 \leq n \leq 500{,}000 $, $ 1 \leq c \leq 10^6 $.
- For each $ i \in [1, n] $: a word $ w_i = (w_{i,1}, w_{i,2}, \dots, w_{i,l_i}) $ with $ l_i \geq 1 $, $ w_{i,j} \in [1, c] $, and $ \sum_{i=1}^n l_i \leq 10^6 $.
Define the shift function $ f_r: [1, c] \to [1, c] $ by:
$$
f_r(x) =
\begin{cases}
x + r & \text{if } x + r \leq c \\
x + r - c & \text{otherwise}
\end{cases}
= ((x - 1 + r) \bmod c) + 1
$$
Let $ w_i^{(r)} = (f_r(w_{i,1}), f_r(w_{i,2}), \dots, f_r(w_{i,l_i})) $.
We seek $ r \in \{0, 1, \dots, c-1\} $ such that:
$$
\forall i \in [1, n-1]:\quad w_i^{(r)} \leq_{\text{lex}} w_{i+1}^{(r)}
$$
If such $ r $ exists, output any such $ r $. Otherwise, output $ -1 $.
API Response (JSON)
{
"problem": {
"name": "D. 80-th Level Archeology",
"description": {
"content": "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 con",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF731D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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 con...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "考古学家在Cycleland一座金字塔的地下墓穴中发现了一条秘密通道。要进入宝库，他们必须打开一扇门上的特殊锁。锁上显示着 #cf_span[n] 个词，每个词由若干象形文字组成。锁旁的墙上有一个圆形开关，每次旋转该开关都会根据特定规则改变所有象形文字。旁边说明指出，只有当锁上的词按字典序排列时，门才会打开（字典序比较的定义见注释部分）。\n\n改变象形文字的规则如下：圆形开关顺时针旋转一次，会将每个...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "Let $ n $ be the number of words, $ c $ the size of the alphabet, and let each word $ w_i $ be a sequence of $ l_i $ integers from $ [1, c] $.\n\nDefine a cyclic shift $ r \\in \\{0, 1, \\dots, c-1\\} $ as ...",
"is_translate": false,
"language": "Formal"
}
]
}