Throughout the long river of history, many important events have occurred, which are known as historical landmarks. Dr, a time-travel enthusiast, is preparing for his time travel.

Dr has categorized his favorite historical landmarks into $n$ types, and the set of historical landmarks of the $i$-th type is denoted as $S_i$, where the occurrence time of the $j$-th historical landmark in the $i$-th set is $S_{i,j}$. Since visiting the same type of historical landmark twice would make Dr bored, he wishes to select exactly one historical landmark from each type to visit.

Because visiting $n$ landmarks in one go is too exhausting, Dr decides to divide the trip into $k$ time travels. For each time travel, he can choose any historical landmark from any unvisited set as a starting point, and then visit historical landmarks sequentially through time jumps. However, time travel is not an easy task; each time travel must end by returning to the starting point of that trip via a time jump, otherwise, it is impossible to ensure a return to the original timeline. Additionally, each trip must consist of an odd number of time jumps to avoid causing chaos in the timeline.

Time jumps can transport Dr from one historical landmark to another, but if the occurrence time of the starting landmark and the ending landmark are too close, it will slightly affect the timeline. Therefore, Dr hopes to plan his time travel scheme such that the distance between the starting and ending points of every time jump is as large as possible, thereby minimizing his impact on the timeline. This means he wants to maximize the minimum time difference among all time jumps in the $k$ trips.

If Dr cannot traverse the $n$ types of landmarks in exactly $k$ trips, output Impossible.

Note:

1. Even if two historical landmarks occur at the same time, because they occur at different locations, Dr can only visit one of them after a jump, not all historical landmarks at that time point.

2. If a trip visits only one point, then no time jumps were performed during this trip, and there is no impact on the timeline.

Problem Summary: Select one number from each of the $n$ multisets to form a set $T$ of size $n$, and arrange $T$ into $k$ odd cycles, maximizing the minimum difference between adjacent points in all cycles.

Input

The first line contains two integers $n$ and $k$, representing the number of types of historical landmarks and the number of time travels Dr plans to make.

The next $n$ lines each start with a positive integer $t_i$, representing that there are $t_i$ historical landmarks of the $i$-th type. This is followed by $t_i$ integers, where the $j$-th integer represents the occurrence time of the $j$-th historical landmark of the $i$-th type.

Output

Output an integer representing the maximum possible value of the minimum time difference between all time jumps.

Examples

Input 1

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

Output 1

Impossible

Input 2

4 2
2 2 4
1 4
2 6 12
1 7

Output 2

5

Note 2

Select the $n$ historical nodes as $[2, 4, 12, 7]$. The first trip route is $[2 \to 7 \to 12 \to 2]$, and the second trip route is $[4]$.

Input 3

9 3
2 7 1
1 4
2 4 5
1 8
2 5 4
1 7
2 7 2
1 8
1 2

Output 3

3

Note 3

Select the $n$ historical nodes as $[1, 4, 5, 8, 5, 7, 2, 8, 2]$. The first trip route is $[1 \to 4 \to 7 \to 1]$, the second trip route is $[2 \to 5 \to 8 \to 2]$, and the third trip route is $[2 \to 5 \to 8 \to 2]$.

Subtasks

• Subtask 1 (3pts): $2 \le n \le 300, k=1, |S_i|=1$, and all historical landmark occurrence times are exactly a permutation of $1$ to $n$.
• Subtask 2 (8pts): $2 \le n \le 15, 1 \le k < n, |S_i| \le 2, 0 \le S_{i,j} \le 10^{18}$.
• Subtask 3 (5pts): $2 \le n \le 300, k=1, |S_i|=1, 0 \le S_{i,j} \le 10^{18}$.
• Subtask 4 (12pts): $2 \le n \le 300, 1 \le k < n, |S_i|=1, 0 \le S_{i,j} \le 10^{18}$.
• Subtask 5 (15pts): $2 \le n \le 100, 1 \le k < n, |S_i| \le 2, 0 \le S_{i,j} \le 10^{18}$.
• Subtask 6 (24pts): $2 \le n \le 200, 1 \le k < n, |S_i| \le 4, 0 \le S_{i,j} \le 10^{18}$.
• Subtask 7 (33pts): $2 \le n \le 300, 1 \le k < n, |S_i| \le 5, 0 \le S_{i,j} \le 10^{18}$.