CF212B Polycarpus is Looking for Good Substrings

我们把字符串 $ s[a,b]=s_{a}s_{a+1}...\ s_{b} $ $ (1\le a\le b\le |s|) $ 叫做字符串 $ s=s_{1}s_{2}\dots s_{|s|} $ 的一个子串。其中 $ |s| $ 是字符串 $ s $ 的长度。 一个非空字符串 $ t $ 的字符集是包含了字符串 $t$ 中的字符的集合。比如，字符串 `"aab"` 的字符集是 `{'a','b'}`。 让我们把 $C$ 定义为一个任意字符串 $s$ 的子串的字符集。我们将 $r(C,s)$ 叫做 $s$ 的满足字符集为 $C$ 的子串组成的集合中极大内含的数量。而如果对于由子串组成的集合中某个子串 $ s[a,b] $（设其长度为 $ n=b-a+1 $）, 不存在子串 $ s[x,y] $ 长度大于 $ n $ 且 $ 1\le x \le a\le b\le y\le |s| $，那它是这个集合中的一个极大内含。 $ s $ 的两个子串不管内容是否一样，只要位置不同，就会被认定为是不同的。 Polycarpus 在字符串学课上得到了一个有挑战性且实际的一个任务。他必须要对于给定的字符串 $s$ 和字符集 $C_{1},C_{2},\dots,C_{m}$，算出 $ r(C_{i},s)$ $(i\in[1,m])$。 Polycarpus 不想被大学驱逐而参军，所以请帮助他解决这个问题。

第一行是一个非空字符串 $ s $ $ (1\le |s|\le 10^{6}) $。 第二行是一个整数 $ m $ $ (1\le m\le 10^{4}) $。接下来 $ m $ 行，第 $i$ 行是一个字符串 $ c_{i} $，其字符集是 $ C_{i} $。保证每一行中的 $c_i$ 中字符不重复。 注意 $ C_{i} $ 不一定不相同。所有给定的字符串仅包含英文小写字母。

输出 $ m $ 个整数，第 $i$ 个整数等于 $ r(C_{i},s) $。