#include using namespace std; #define sim template < class c #define ris return * this #define dor > debug & operator << #define eni(x) sim > typename \ enable_if(0) x 1, debug&>::type operator<<(c i) { sim > struct rge { c b, e; }; sim > rge range(c i, c j) { return rge{i, j}; } sim > auto dud(c* x) -> decltype(cerr << *x, 0); sim > char dud(...); struct debug { #ifdef LOCAL ~debug() { cerr << endl; } eni(!=) cerr << boolalpha << i; ris; } eni(==) ris << range(begin(i), end(i)); } sim, class b dor(pair < b, c > d) { ris << "(" << d.first << ", " << d.second << ")"; } sim dor(rge d) { for (auto it = d.b; it != d.e; ++it) *this << ", \0[" + 3 * (it == d.b) << *it; ris << "]"; } #else sim dor(const c&) { ris; } #endif }; #define imie(x) "[" << #x ": " << (x) << "] " const int nax=2000*1007; int n; char wcz[nax]; int l; int dzie[nax][30]; int war[nax]; int oj[nax]; int suf[nax]; vector ctree[nax]; vector kon[nax]; long long dod[nax]; long long wyn[nax]; int q; int lew[nax]; int pra[nax]; vector co_tu[nax]; void sufy() { queue bfs; bfs.push(0); while(!bfs.empty()) { int v=bfs.front(); bfs.pop(); for (int i=0; i<26; i++) if (dzie[v][i]) bfs.push(dzie[v][i]); if (!oj[v]) continue; int w=suf[oj[v]]; while(w && !dzie[w][war[v]]) w=suf[w]; suf[v]=dzie[w][war[v]]; } for (int i=1; i<=l; i++) ctree[suf[i]].push_back(i); } long long drzewo[nax]; void dodaj(int v, long long w) { debug() << "wale w " << v; for (int i=v; i<=n; i+=(-i&i)) drzewo[i]+=w; } long long czytaj(int v, int u) { debug() << "z " << v << " " << u; long long ret=0; for (int i=v-1; i; i-=(-i&i)) ret-=drzewo[i]; for (int i=u; i; i-=(-i&i)) ret+=drzewo[i]; return ret; } void dfs(int v) { debug() << imie(v); for (int i=0; i