class StringHash {

public:
    int size;
    char *array;
    char *array_forward;
    unsigned long long* pre_base;
    unsigned long long* hash_array;
    unsigned long long* hash_array_forward;
    unsigned long long base = 12582917;

    StringHash(int size) : size(size) {
        array = new char[size + 1];
        pre_base = new unsigned long long[size + 1];
        hash_array = new unsigned long long[size + 1];
        std::memset(array, 0, size + 1);
        std::memset(pre_base, 0, size + 1);
        std::memset(hash_array, 0, size + 1);
    }

    ~StringHash() {
        delete[] array;
        delete[] hash_array;
        delete[] pre_base;
        delete[] array_forward;
        delete[] hash_array_forward;
    }

    void input(string t)
    {
        for(int i=0;i<t.size();i++)
            array[i+1]=t[i];
    }

    friend std::ostream& operator<<(std::ostream& os, const StringHash& customStruct) {
        os << customStruct.array+1; // Output the array to the output stream
        return os;
    }

    void init()
    {
        pre_base[0]=1;
        for(int i=1;i<=size;i++)
        pre_base[i]=base*pre_base[i-1];

        hash_array[0]=0;
        for(int i=1;i<=size;i++)
        {
           hash_array[i]=hash_array[i-1]*base;
           hash_array[i]+=array[i];
        }

    }

    void open_parall()
    {
        hash_array_forward = new unsigned long long[size + 1];
        array_forward = new char[size + 1];
        std::memset(hash_array_forward, 0, size + 1);
        std::memset(array_forward, 0, size + 1);
        for(int i=size;i>=1;i--)
        {
           array_forward[i]=array[size-i+1];
        }
        for(int i=1;i<=size;i++)
        {
           hash_array_forward[i]=hash_array_forward[i-1]*base;
           hash_array_forward[i]+=array_forward[i];
        }
    }

    unsigned long long getHash(int l,int r)
    {
       return hash_array[r]-hash_array[l-1]*pre_base[r-l+1];
    }

    bool is_paralld(int l,int r)
    {
        return getHash(l,r)==getHash(size-r+1,size-l+1,hash_array_forward);
    }

    unsigned long long getHash(int l,int r,unsigned long long* Hash)
    {
       return Hash[r]-Hash[l-1]*pre_base[r-l+1];
    }

};