如果可以重新排列字符串 $$$s$$$ 中的符号来获得等于 $$$t$$$ 的字符串,那么我们将两个字符串 $$$s$$$ 和 $$$t$$$ 称为字谜词。
让我们考虑两个字符串 $$$s$$$ 和 $$$t$$$,它们是彼此的字谜词。如果存在满足以下条件的整数 $$$k \ge 2$$$ 和 $$$2k$$$ 非空字符串 $$$s_1, t_1, s_2, t_2, \dots, s_k, t_k$$$,我们说 $$$t$$$ 是 $$$s$$$ 的可约字谜:
1. 如果我们按顺序写入字符串 $$$s_1, s_2, \dots, s_k$$$,则结果字符串将等于 $$$s$$$;
2. 如果我们按顺序写入字符串 $$$t_1, t_2, \dots, t_k$$$,则结果字符串将等于 $$$t$$$;
3. 对于 $$$1$$$ 和 $$$k$$$ 之间的所有整数 $$$i$$$,$$$s_i$$$ 和 $$$t_i$$$ 是彼此的字谜词。
如果这样的字符串不存在,则 $$$t$$$ 被认为是 $$$s$$$ 的不可约字谜。请注意,仅当 $$$s$$$ 和 $$$t$$$ 互为字谜时才定义这些概念。
例如,考虑字符串 $$$s = $$$ "gamegame"。那么字符串 $$$t = $$$ "megamage" 是 $$$s$$$ 的可简化字谜,我们可以选择例如 $$$s_1 = $$$ "game", $$$s_2 = $$$ "gam", $$$s_3 = $$$ "e" 和 $$$t_1 = $$$ "mega", $$$t_2 = $$$ "mag", $$$t_3 = $$$“e”:
另一方面,我们可以证明 $$$t = $$$ "memegaga" 是 $$$s$$$ 的不可约字谜。
您将获得一个字符串 $$$s$$$ 和 $$$q$$$ 查询,由两个整数 $$$1 \le l \le r \le |s|$$$ 表示(其中 $$$|s|$$$ 等于字符串 $$$s$$$ 的长度)。对于每个查询,您应该查找从 $$$l$$$-th 到 $$$r$$$-th 的字符组成的 $$$s$$$ 的子字符串是否至少有一个不可约的字谜词。
输入
第一行包含一个字符串 $$$s$$$,由小写英文字符组成 ($$$1 \le |s| \le 2 \cdot 10^5$$$)。
第二行包含一个整数 $$$q$$$ ($$$1 \le q \le 10^5$$$) — 查询数。
以下$$$q$$$ 行均包含两个整数$$$l$$$ 和$$$r$$$ ($$$1 \le l \le r \le |s|$$$),表示对由第$$$l$$$ 到第$$$r$$$ 字符组成的$$$s$$$ 子字符串的查询。
输出
对于每个查询,如果相应的子字符串至少有一个不可约的字谜,则打印一行包含“Yes”(不带引号)的行,否则打印一行包含“No”(不带引号)的行。
示例
输入 #1
aaaaa 3 1 1 2 4 5 5
输出 #1
Yes No Yes
输入 #2
aabbbbbbc 6 1 2 2 4 2 2 1 9 5 7 3 5
输出 #2
No Yes Yes Yes No No
注意
在第一个示例中,在第一个和第三个查询中,子字符串是“a”,它本身就是一个不可约的字谜词,因为两个或多个非空字符串不能放在一起以获得“a”。另一方面,在第二个查询中,子字符串是“aaa”,它没有不可约的字谜:它唯一的字谜是它本身,我们可以选择 $$$s_1 = $$$ "a", $$$s_2 = $$$ "aa", $$$t_1 = $$$ "a", $$$t_2 = $$$ "aa" 来表明它是一个可约的字谜。
在第二个样本的第二个查询中,子字符串是“abb”,例如,“bba”是不可约的字谜词。