CF1290B.Irreducible Anagrams

Let's call two strings $s$ and $t$ anagrams of each other if it is possible to rearrange symbols in the string $s$ to get a string, equal to $t$.

Let's consider two strings $s$ and $t$ which are anagrams of each other. We say that $t$ is a reducible anagram of $s$ if there exists an integer $k \ge 2$ and $2k$ non-empty strings $s_1, t_1, s_2, t_2, \dots, s_k, t_k$ that satisfy the following conditions:

1. If we write the strings $s_1, s_2, \dots, s_k$ in order, the resulting string will be equal to $s$;
2. If we write the strings $t_1, t_2, \dots, t_k$ in order, the resulting string will be equal to $t$;
3. For all integers $i$ between $1$ and $k$ inclusive, $s_i$ and $t_i$ are anagrams of each other.

If such strings don't exist, then $t$ is said to be an irreducible anagram of $s$. Note that these notions are only defined when $s$ and $t$ are anagrams of each other.

For example, consider the string $s = $ "gamegame". Then the string $t = $ "megamage" is a reducible anagram of $s$, we may choose for example $s_1 = $ "game", $s_2 = $ "gam", $s_3 = $ "e" and $t_1 = $ "mega", $t_2 = $ "mag", $t_3 = $ "e":

On the other hand, we can prove that $t = $ "memegaga" is an irreducible anagram of $s$.

You will be given a string $s$ and $q$ queries, represented by two integers $1 \le l \le r \le |s|$ (where $|s|$ is equal to the length of the string $s$). For each query, you should find if the substring of $s$ formed by characters from the $l$-th to the $r$-th has at least one irreducible anagram.

我们称两个字符串 $s$ 和 $t$ 互为变位词（anagram），如果可以通过重排字符串 $s$ 中的字符得到与 $t$ 相等的字符串。

考虑两个互为变位词的字符串 $s$ 和 $t$。若存在整数 $k \ge 2$ 以及 $2k$ 个非空字符串 $s_1, t_1, s_2, t_2, \dots, s_k, t_k$，满足以下条件，则称 $t$ 是 $s$ 的一个可约变位词（reducible anagram）：

1. 将字符串 $s_1, s_2, \dots, s_k$ 按顺序拼接，所得字符串等于 $s$；
2. 将字符串 $t_1, t_2, \dots, t_k$ 按顺序拼接，所得字符串等于 $t$；
3. 对每个 $i = 1, 2, \dots, k$，$s_i$ 与 $t_i$ 互为变位词。

若不存在满足上述条件的字符串，则称 $t$ 是 $s$ 的一个不可约变位词（irreducible anagram）。注意：上述概念仅在 $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$ 的长度）。对每个查询，你需要判断：由 $s$ 的第 $l$ 个字符到第 $r$ 个字符构成的子串是否至少存在一个不可约变位词。

The first line contains a string $s$, consisting of lowercase English characters ($1 \le |s| \le 2 \cdot 10^5$).

The second line contains a single integer $q$ ($1 \le q \le 10^5$) — the number of queries.

Each of the following $q$ lines contain two integers $l$ and $r$ ($1 \le l \le r \le |s|$), representing a query for the substring of $s$ formed by characters from the $l$-th to the $r$-th.

第一行包含一个字符串 $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|$），表示对字符串 $s$ 中从第 $l$ 个字符到第 $r$ 个字符所构成的子串进行一次查询。

For each query, print a single line containing "Yes" (without quotes) if the corresponding substring has at least one irreducible anagram, and a single line containing "No" (without quotes) otherwise.

对于每个查询，如果对应的子串至少存在一个不可约异位词，则输出一行“Yes”（不带引号）；否则输出一行“No”（不带引号）。

In the first sample, in the first and third queries, the substring is "a", which has itself as an irreducible anagram since two or more non-empty strings cannot be put together to obtain "a". On the other hand, in the second query, the substring is "aaa", which has no irreducible anagrams: its only anagram is itself, and we may choose $s_1 = $ "a", $s_2 = $ "aa", $t_1 = $ "a", $t_2 = $ "aa" to show that it is a reducible anagram.

In the second query of the second sample, the substring is "abb", which has, for example, "bba" as an irreducible anagram.

在第一个样例中，第一次和第三次查询的子串均为 “a”，它自身即为一个不可约变位词，因为无法用两个或更多个非空字符串拼接得到 “a”。另一方面，在第二次查询中，子串为 “aaa”，它没有不可约变位词：其唯一的变位词就是它自身；我们可取 $s_1 = $ “a”、$s_2 = $ “aa”、$t_1 = $ “a”、$t_2 = $ “aa”，从而说明它是可约变位词。

在第二个样例的第二次查询中，子串为 “abb”，它具有例如 “bba” 这样的不可约变位词。