CF367A Sereja and Algorithm

Sereja 喜欢各种算法。他最近想出了一个新算法，该算法以一个字符串作为输入。我们用 $q=q_1q_2\dots q_k$ 表示算法的输入字符串。该算法包括以下两个步骤： 1. 找到字符串 $q$ 的任意一个长度为三的连续子序列（子串），该子串**不等于**"zyx"、"xzy"、"yxz"中的任意一个。如果 $q$ 不包含这样一个子串，则终止算法，否则进入第 2 步。 2. 随机重排列找到的该子串的字母，然后回到第 1 步。 Sereja 认为，如果存在非零概率该算法会被终止，那么算法对字符串 $q$ 能正确运行。但如果算法无论如何也会无限运行下去，则认为算法对该字符串运行不正确。 Sereja 想测试他的算法。为此，他有一个长度为 $n$ 的字符串 $s=s_1s_2\dots s_n$。这个字符串只包含字符 'x'、'y'、'z'。他会进行 $m$ 次测试。对于第 $i$ 次测试，他会把子串 $s_{l_i}s_{l_i+1}\dots s_{r_i}$ （$1\le l_i\le r_i\le n$）作为算法的输入。遗憾的是，他实现的算法太慢了，所以他请求你的帮助。对于每次测试 $(l_i, r_i)$，请你判断算法在本次测试的子串上是否能正确终止。

第一行为一个非空字符串 $s$，其长度 $n$ 不超过 $10^5$。保证 $s$ 只包含字符 'x'、'y'、'z'。 第二行为一个整数 $m$，表示测试次数（$1\le m\le 10^5$）。接下来 $m$ 行，每行两个整数 $l_i$ 和 $r_i$（$1\le l_i\le r_i\le n$），表示一次测试。

对于每次测试，若算法能正确终止则输出 "YES"（不带引号），否则输出 "NO"（不带引号）。

在第一个样例中，对于测试 1 和 2，算法总能在一步内终止。在第 4 个测试中，可以得到字符串 "xzyx"，在该字符串下算法会终止。所有其他测试下算法都不能正确终止。 由 ChatGPT 5 翻译