After a long period working in his magical garden, Bratan Mahammad could grow flowers of N distinct kinds there. Since Tukezban's (Mahammad's love) birthday is coming, as a perfect gift, Mahammad wants to give her K bunches of flowers. Interestingly, each flower has a beautifulness x_i and the number of flowers of every kind is M. When preparing flower buckets, he has to be very careful: every bucket must consist of N flowers and surely, all flowers have to be distinct kind in each bucket. The overall beauty value of K buckets depends on the absolute difference between the beautifulness of the most beautiful flower of K buckets (max(x_i)) and the least beautiful one (min(x_i)). Help Mahammad minimize this difference.

Input

The first line of the input contains 3 positive integers, N, M and K, denoting the number of flower types, the number of flowers in each type, and the number of buckets needed, respectively. Then, the following N lines have 4 integers each, x_i,1, a_i, b_i, c_i.

Here x_i,1 indicates the beautifulness of the first flower in i-th type. And for remaining M - 1 flowers, beautifulness value is calculated as x_{i, j} = (a_i * x_{i, j-1} + b_i) % c_i .

You can safely assume that  N, M, K ≤ 2500 and K ≤ M. All numbers in input section fit 32-bit signed nonnegative integers.

Output

Print the minimum possible difference in K-buckets. 

Example

Input:
2 3 2
2 2 3 9
2 1 2 10 

Output:
4

Note:

The generated beauty values will be:

For i = 1: (2, 7, 8)

For i = 2: (2, 4, 6)

One optimal way is to choose buckets as (7, 4) and (8, 6) together, so the difference is |8 - 4| = 4

By the way, we should not choose (2, 4) and (7, 2), since |7 - 2| = 5, which is greater than 4.