#SELECTION. Bucket Selection

Bucket Selection

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 xi 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(xi)) and the least beautiful one (min(xi)). 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, xi,1, ai, bi, ci.

Here xi,1 indicates the beautifulness of the first flower in i-th type. And for remaining M - 1 flowers, beautifulness value is calculated as xi, j = (ai * xi, j-1 + bi) % ci .

You can safely assume that N, M, K ≤ 2500 and K ≤ M. All numbers in input section fit 32-bit signed non-negative 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

</p>

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.