There are N classes in a school, each with M students. There is going to be a race of 100m dash, and a representative from each class will be chosen to participate in this race. You were assigned a task to choose these representatives. Since you did not want the race to be one sided, you wanted to choose the representatives such that the difference between the ability of the best representative and the worst representative is minimal.

For example, if N = 3 and M = 4, and each class has students with following abilities:

Class 1: {12,16,67,43}

Class 2: {7,17,68,48}

Class 3: {14,15,77,54}

it is best to choose the student with ability 16 from Class 1, 17 from Class 2, and 15 from Class 3. Thus, the difference in this case would be 17-15 = 2.

Your task is to calculate the minimal possible difference you can achieve by choosing a representative from each class.

Input

The first line of the input consists of two integers, N and M. (1<=N<=1000, 1<=M<=1000).

The next N lines will have M integers. The jth element of ith line is the ability of the jth student in ith class. The number is between 0 and 10^9, inclusive.

Output

Output the minimal difference one can achieve by choosing the representative from each class.

Example

Input:
3 4
12 16 67 43
7 17 68 48
14 15 77 54


Output:
2

Input:
4 3
10 20 30
40 50 60
70 80 90
100 110 120

Output:
70