80-th Level Archeology

Description:

Input:

The first line of the input contains two integers n and c (2 ≤ n ≤ 500 000, 1 ≤ c ≤ 10⁶) — 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, li (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 10⁶.

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.

Sample Input:

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

Sample Output:

1

Sample Input:

2 5
2 4 2
2 4 2

Sample Output:

0

Sample Input:

4 4
1 2
1 3
1 4
1 2

Sample Output:

-1

Note:

Word a₁, a₂, ..., a_m of length m is lexicographically not greater than word b₁, b₂, ..., 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.