← 返回题目列表

Codeforces · 367/A

A. Sereja 和算法

中文机器翻译题面 查看原题

Sereja 喜欢各种算法。他最近提出了一种新算法,该算法接收字符串作为输入。让我们将算法的输入字符串表示为 q = q1q2...qk。该算法由两个步骤组成:

1. 查找字符串 q 中三个字符的任意连续子序列(子串),且该子序列不等于字符串“zyx”、“xzy”、“yxz”。如果 q 不包含任何此类子序列,则终止算法,否则转到步骤 2。
2.将找到的子序列的字母随机重新排列,然后转到步骤1。

Sereja 认为,如果算法终止的概率非零,则该算法对字符串 q 可以正确工作。但是,如果该算法无论如何都可以在字符串上无限长地工作,那么我们认为该算法在该字符串上工作不正确。

Sereja 想要测试他的算法。为此,他有字符串 s = s1s2... sn,由 n 个字符组成。男孩进行了一系列 m 测试。作为第 i 个测试,他将子字符串 slisli + 1... sri (1 ≤ li ≤ ri ≤ n) 发送到算法输入。不幸的是,他的算法的实现时间太长,所以 Sereja 请你帮忙。对于每个测试(li,ri),确定算法在此测试中是否正常工作。

输入

第一行包含非空字符串 s,其长度 (n) 不超过 105。保证字符串 s 只包含字符:'x'、'y'、'z'。

第二行包含整数 m (1 ≤ m ≤ 105) — 测试次数。接下来的 m 行包含测试。第 i 行包含一对整数 li, ri (1 ≤ li ≤ ri ≤ n)。

输出

对于每个测试,如果算法在相应的测试中正常工作,则打印“YES”(不带引号),否则打印“NO”(不带引号)。

示例

输入 #1

zyxxxxxxyyz
5
5 5
1 3
1 11
1 4
3 6

输出 #1

YES
YES
NO
YES
NO

注意

在第一个示例中,在测试一和测试二中,算法将始终在一步中终止。在第四个测试中,您可以获得字符串“xzyx”,算法将在该字符串上终止。在所有其他测试中,该算法无法正常工作。