T774800 Sam的弱循环节

题目描述

Sam 最近在学习 $Hash$ 算法，$Hash$ 算法有一个经典的应用就是进行字符串匹配求一个字符串的循环节长度。

于是 Sam 准备自己生成一些字符串当做测试数据，测试代码是否正确。

他会先自己随机写一个仅包含大小写字母的字符串 $S$。

然后用以下代码依次生成一个字符串序列 $A_0 \sim A_n$：

int n = S.size();
A[0] = "";
for (int i = 1; i <= n; i++){
	if (S[i - 1] >= 'A' && S[i - 1] <= 'Z'){
		A[i] = A[i - 1] + char(S[i - 1] + 32);
	} else {
		A[i] = S[i - 1] + A[i - 1];
	}
}

但是 Sam 觉得求循环节太简单了，于是他设计了一个新的概念——弱循环节。

对于一个字符串 $B$ 来说，一个整数 $len$ 如果满足对于任意 $B_i = B_{i+len}(1 \leq i \leq |B| - len)$，那么就认为 $len$ 是 $B$ 的一个弱循环节，一个字符串可能有多个弱循环节。

例如 $ABCAB$ 的弱循环节有两个，分别是 $3$ 和 $5$。

单纯求字符串的弱循环节也还是过于简单了。

于是 Sam 会给出一个序列 $a_1 \sim a_m$，并给出 $T$ 次询问。

第 $i$ 次询问 Sam 会给出三个整数 $l_i, r_i, pos_i$，你的任务是在 $a$ 序列中找出一个 $a_x$ 满足 $x \in [l_i,r_i]$ 且 $a_x$ 是 $A_{pos_i}$ 的弱循环节，如果有多个满足条件的 $a_x$ 请输出最小的 $a_x$（数值最小而不是 $x$ 最小）。

输入格式

输入第一行包含一个字符串 $S$，保证仅由大小写字母组成。

输入第二行包含一个整数 $m$，表示序列 $a$ 的长度。

输入第三行包含 $m$ 个整数，分别表示 $a_i$。

输入第四行包含一个整数 $T$，表示询问次数。

接下来 $T$ 行，每行包含三个整数 $pos_i,l_i,r_i$，表示一次询问。

输出格式

对于每次询问，输出一个整数，表示第 $i$ 次询问的答案，如果不存在符合条件的 $a_x$，则输出 No answer!。

输入输出样例 #1

输入 #1

AABAAba
9
4 3 2 1 7 5 3 6 1
6
1 4 4
2 1 4
2 1 3
3 3 5
5 4 7
7 8 9

输出 #1

1
1
2
No answer!
3
6

说明/提示

数据范围

对于 $20\%$ 的数据满足 $n,m,T \leq 100$。

对于另外 $20\%$ 的数据满足 $r_i - l_i \leq 100$。

对于另外 $20\%$ 的数据满足 $a$ 序列单调不减。

对于 $100\%$ 的数据满足 $1 \leq n,m,T \leq 500000, 1 \leq a_i,pos_i \leq n, 1\leq l_i \leq r_i \leq m$。

样例解释

对应的 $A$ 序列分别为：

$A[1] = a$

$A[2] = aa$

$A[3] = aab$

$A[4] = aaba$

$A[5] = aabaa$

$A[6] = baabaa$

$A[7] = abaabaa$

对于第一次询问，$A[1]=a$，所以满足条件的弱循环节长度为 $1$。 对于第二次询问，$A[2]=aa$，所以满足条件的弱循环节长度为 $1,2$，最小的是 $1$。 对于第三次询问，满足条件的只有 $2$，所以答案是 $2$。