// -----------------------------------------------------------------------------
// Rolling Hash                                                               C#
// -----------------------------------------------------------------------------

class RollingHash
{
    int mod = 0;
    int mul = 0;
    int maxlen = 0;
    long[] R = null;

    public RollingHash(int mod, int mul, int maxlen)
    {
        this.mod = mod;
        this.mul = mul;
        this.maxlen = maxlen;
        R = new long[maxlen];
        R[0] = 1;
        for (int i = 1; i < maxlen; i++)
            R[i] = (R[i - 1] * mul) % mod;
    }

    public RollingHash(int maxlen) : this(2147483647, 48271, maxlen) { }

    long hash = 0;

    public string Text { get; private set; }
    public int Offset { get; private set; }
    public int Length { get; private set; }

    public int Hash(string text)
    {
        return Hash(text, 0, text.Length);
    }

    public int Hash(string text, int offset, int length)
    {
        Text = text;
        Offset = offset;
        Length = length;
        hash = 0;
        for (int i = offset; i < offset + length; i++)
            hash = ((hash * mul) + text[i]) % mod;
        return (int)hash;
    }

    public int Hash(int hash, int offset, int length)
    {
        this.hash = hash;
        Offset = offset;
        Length = length;
        return hash;
    }

    public int Roll()
    {
        if (Offset + Length < Text.Length)
        {
            hash = (hash + mod - (R[Length - 1] * Text[Offset]) % mod) % mod;
            hash = ((hash * mul) + Text[Offset + Length]) % mod;
            Offset++;
        }
        return (int)hash;
    }

    public int RollOffset()
    {
        if (Length > 1)
        {
            hash = (hash + mod - (R[Length - 1] * Text[Offset]) % mod) % mod;
            Length--;
        }
        return (int)hash;
    }

    public int RollLength()
    {
        if (Offset + Length < Text.Length)
        {
            hash = ((hash * mul) + Text[Offset + Length]) % mod;
            Length++;
        }
        return (int)hash;
    }
}

// -----------------------------------------------------------------------------