A virologist conducted experiments on $K$ strains of a virus and recorded the temperatures at which each strain dies. The number of experiments for each strain may vary. We define the size of a temperature range that kills all virus strains as the difference between the boundaries of a range that contains at least one temperature for the destruction of each virus strain. Help the virologist determine the minimum possible size of such a range.

Input

The first line contains a single positive integer $K$ — the number of virus strains, $1 \leqslant K \leqslant 10^5$. Following this are $K$ lines, each containing space-separated integers. In the $i$-th line, the first number $M_i$ is the number of experiments on the $i$-th strain that resulted in the destruction of the strain, $1 \leqslant M_i \leqslant 10^5$, followed by $M_i$ temperature values from the experiments in which the strain died, with all values in the range from $-10^7$ to $10^7$. The total number of experiments conducted across all virus strains does not exceed $10^5$.

Output

A single integer — the minimum possible size of the temperature range that is lethal for all virus strains.

Examples

Input 1

3
5 3 9 15 24 20
4 1 9 13 14
4 5 15 12 11

Output 1

1