const int N = 2e6+10;

int tot;

int ch[N][26], ch2[N][26];

int fail[N], val[N], sum[N], sz[N], End[N];

char s[N];

vector<int> g[N];

queue<int> q, Q;

struct AC_automaton {

	int T;

	void newnode(int &o) {

		if (Q.size()) {o = Q.front(); Q.pop();}

		else o=++tot;

		memset(ch[o],0,sizeof ch[o]);

		val[o] = sum[o] = sz[o] = 0;

	}

	void add(int &o, char *s, int v, int id) {

		if (!o) newnode(o);

		if (*s) add(ch[o][*s-'a'],s+1,v,id);

		else val[o] += v, End[id] = o;

	}

	void add(char *s, int v, int id) {

		add(T,s,v,id);

	}

	void build() {

		REP(i,0,25) ch2[T][i]=T;

		q.push(T), fail[T]=T;

		while (q.size()) {

			int x = q.front(); q.pop();

			sum[x] = sum[fail[x]]+val[x];

			REP(i,0,25) {

				if (ch[x][i]) {

					int y = ch[x][i];

					q.push(y);

					fail[y] = ch2[fail[x]][i];

					ch2[x][i] = y;

					g[fail[y]].pb(y);

				} else ch2[x][i] = ch2[fail[x]][i];

			}

		}

	}

	void dfs(int x) {

		for (int y:g[x]) dfs(y),sz[x]+=sz[y];

	}

	int query(char *s) {

		int n = strlen(s), now = T, ans = 0;

		REP(i,0,n-1) {

			now = ch2[now][s[i]-'a'];

			ans += sum[now], ++sz[now];

		}

		dfs(T);

		return ans;

	}

	void dfs2(int x) {

		for (int y:g[x]) dfs2(y);

		Q.push(x),g[x].clear();

	}

	void clear() {

		if (T) dfs2(T),T=0;

	}

} ac;