public class KSubstring
{
    bool Compatible(SumIndices indices1, SumIndices indices2, int len)
    {
        return Compatible(indices1.Left, indices2.Right, len) || Compatible(indices2.Left, indices1.Right, len);
    }

    private bool Compatible(int left, int right, int len)
    {
        return left + len <= right;
    }

    class SumIndices
    {
        public int Left;
        public int Right;
        public long Sum;

        public SumIndices(int left, int right, long sum)
        {
            Left = left;
            Right = right;
            Sum = sum;
        }
    }

    class SumEntry : IComparable<SumEntry>
    {
        public long Sum;
        public int Idx;

        public SumEntry(long sum, int idx)
        {
            Sum = sum;
            Idx = idx;
        }

        public int CompareTo(SumEntry other)
        {
            if (Sum != other.Sum)
                return Sum.CompareTo(other.Sum);
            return Idx.CompareTo(other.Idx);
        }
    }

    public int[] maxSubstring(int A0, int X, int Y, int M, int n)
    {
        long[] A = new long[n];
        A[0] = A0;
        for (int i = 1; i < n; i++)
            A[i] = (A[i - 1] * X + Y) % M;

        long resDiff = int.MaxValue;
        int resLen = -1;
        for (int len = n / 2; len >= 1; len--)
        {
            long[] sums = new long[n - len + 1];
            for (int i = 0; i < len; i++)
                sums[0] += A[i];
            for (int i = 1; i < sums.Length; i++)
                sums[i] = sums[i - 1] + A[i + len - 1] - A[i - 1];
            
            SumEntry[] sumEntries = new SumEntry[sums.Length];
            for (int i = 0; i < sums.Length; i++)
                sumEntries[i] = new SumEntry(sums[i], i);
            Array.Sort(sumEntries);

            List<SumIndices> sumIndices = new List<SumIndices>();
            int left = 0;
            while (left < sumEntries.Length)
            {
                int right = left;
                while (right + 1 < sumEntries.Length && sumEntries[right + 1].Sum == sumEntries[left].Sum)
                    right++;
                sumIndices.Add(new SumIndices(sumEntries[left].Idx, sumEntries[right].Idx, sumEntries[left].Sum));
                left = right + 1;
            }

            SumIndices prev = null;
            foreach (SumIndices cur in sumIndices)
            {
                if (Compatible(cur.Left, cur.Right, len))
                    return new int[] { len, 0 };
                if (prev != null && Compatible(prev, cur, len))
                {
                    long ndiff = Math.Abs(prev.Sum - cur.Sum);
                    if (ndiff < resDiff)
                    {
                        resDiff = ndiff;
                        resLen = len;
                    }
                }
                prev = cur;
            }
        }
        return new int[] { resLen, (int) resDiff };
    }
}