### Прямой и обратный хеш по модулю 2^64

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define long ll
#define all(x) begin(x), end(x)

const int N = 1e6;
const int P = 257;
uint64_t p_pow[N];

struct Initialization {
    Initialization() {
        p_pow[0] = 1;
        for (int i = 1; i < N; ++i) {
            p_pow[i] = p_pow[i - 1] * P;
        }
    }
} init;

struct Forward_Binary_Hash {
    int n;
    string s;
    vector<uint64_t> h;

    Forward_Binary_Hash(const string &from) :
        n((int)from.size()),
        s(from),
        h(1, 0) {
        h.reserve(n + 1);
        for (char c : s) {
            h.push_back(h.back() * P + c);
        }
    }

    uint64_t operator()(int l, int r) {
        //assert(0 <= l && l <= r && r <= n - 1);
        return h[r + 1] - h[l] * p_pow[r - l + 1];
    }
};

struct Backward_Binary_Hash {
    int n;
    string s;
    vector<uint64_t> h;

    Backward_Binary_Hash(const string &from) :
        n((int)from.size()),
        s(from),
        h(1, 0) {
        h.reserve(n + 1);
        reverse(all(s));
        for (char c : s) {
            h.push_back(h.back() * P + c);
        }
    }

    uint64_t operator()(int revl, int revr) {
        //assert(0 <= revl && revl <= revr && revr <= n - 1);
        int l = n - 1 - revr, r = n - 1 - revl;
        //assert(0 <= l && l <= r && r <= n - 1);
        return h[r + 1] - h[l] * p_pow[r - l + 1];
    }
};

int main() {
#ifdef LC
    assert(freopen("input.txt", "r", stdin));
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    return 0;
}