#include <bits/stdc++.h>

using namespace std;

#define int long long

#define pi acos(-1)

#define all(x) x.begin(), x.end()

#define endl "\n"

#define debg cout << "yes" << endl;

#define fast ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);

#define test int t;cin >> t; while (t--)

#define pb push_back

#define vec vector<int>

#define firs first

#define sec second

#define fo(i, n) for (int i = 0; i < n; i++)

#define rep(i, a, n) for (int i = a; i <= n; i++)

#define ln length()

#define spc(x) cout << x << " ";

#define ent(x) cout << x << "\n";

#define mem(x, v) memset(x, v, sizeof(x));

#define deb(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); debug(_it, args); }

void debug(istream_iterator<string> it) {}

template<typename T, typename... Args>

void debug(istream_iterator<string> it, T a, Args... args) { cerr << *it << " = " << a << endl; debug(++it, args...);}

int add(int a,int b,int mod)

}

int mult(int a,int b,int mod)

}

int power(int a,int b,int mod)

}

int mod_inverse(int a,int mod)

{

return power(a,mod-2,mod);

}

int hashing(string s,int mod)

}

int Hash[1000000];

int inv[1000000];

void init_hashing(string s,int mod)

}

int substring(int l,int r,int mod)

}

int32_t main()

}