#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
const int inf = 0x3f3f3f3f;
const int N = 4e5+7;
const ll mod = 998244353;
using namespace std;
ull hash1=13331;
ull ha[N],pp[N];
ull getha(int l,int r){
    if(l==0) return ha[r];
    return ha[r]-ha[l-1]*pp[r-l+1];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    pp[0]=1;
    for(int i=1;i<N;i++) {
        pp[i]=hash1*pp[i-1];
    }
    string s;
    int len=s.length();
    ha[0]=s[0];
    for(int i=1;i<len;i++)
        ha[i]=ha[i-1]*hash1+s[i];
    return 0;
}