Археологи, найдя секретный ход в подземелье одной из пирамид в Цикляндии, столкнулись с необычным замком на двери в сокровищницу. На замке было написано n слов, каждое из которых состоит из нескольких иероглифов. Рядом с замком на стене был обнаружен необычный круглый рычаг, поворот которого меняет иероглифы, из которых состоят слова на замке, по некоторому принципу. Также рядом с иероглифом была найдена надпись на древнецикляндском, которая гласит, что замок откроется, только если слова, написанные на замке, станут идти в лексикографическом порядке (определение дано в пояснении).
Несмотря на то, что археологи отлично знали весь древнецикляндский алфавит, который состоял из c иероглифов, они никак не могли определить закономерность, по которой меняются буквы. Наконец кто-то догадался позвать вас, главного мыслителя современной Цикляндии. Вам хватило одного взгляда, чтобы понять, что поворот рычага на одну позицию по часовой стрелке заменяет каждый иероглиф на следующий за ним по алфавиту, то есть x-й (1 ≤ x ≤ c - 1) иероглиф превращается в (x + 1)-й, а c-й превращается в первый.
Помогите археологам определить, на сколько позиций по часовой стрелке надо повернуть рычаг, чтобы можно было открыть дверь, либо определите, что требуемого положения рычага не существует, и надо либо искать ещё какой-нибудь потайной рычаг, либо идти за динамитом.
В первой строке находится два числа 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.
4 3
2 3 2
1 1
3 2 3 1
4 2 3 1 2
1
2 5
2 4 2
2 4 2
0
4 4
1 2
1 3
1 4
1 2
-1
Слово a1, a2, ..., am длины m лексикографически не превосходит слова b1, b2, ..., bk длины k, если выполняется одно из двух:
Про последовательность слов говорят, что они идут в лексикографическом порядке, если каждое слово в нём (кроме последнего) лексикографически не превосходит следующего за ним.
В первом примере после поворота рычага на 1 позицию по часовой стрелке слова примут следующий вид:
1 3
2
3 1 2
3 1 2 3
Во втором примере слова уже идут в лексикографическом порядке.
Можно проверить, что в последнем примере, какой бы сдвиг мы ни применили, слова не станут идти в лексикографическом порядке.
| Codeforces Round 376 (Div. 2) |
|---|
| Закончено |
