C. Сэрэжа болон алгоритм

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Сэрэжа бүх эрэмблэлтийн алгоритм-д дуртай. Тэр саяхан шинэ алгоритм бодож олсон ба энэ нь оролтондоо тэмдэгт мөр авдаг. Алгоритмын оролтын тэмдэгт мөрийг $q = q_1 q_2 ... q_k$ гэж үзье. Мөн алгоритм нь хоёр алхамаас бүрдэнэ.

  1. q тэмдэгт мөрөөс дараалсан 3 үсгээс бүрдсэн дэд тэмдэгт мөр сонгож авах ба энэ нь "zyx", "xzy", "yxz" –ийн алинтай нь ч адилхан байх ёсгүй. Хэрэв тийм дэд тэмдэгт мөр олдохгүй бол алгоритм дуусна. Бусад тохиолдолд 2 дугаар алхам руу шилжинэ.

  2. Сонгогдсон дэд тэмдэгт мөрийн үсэгнүүдээ дурын байрлалаар нь сольж 1 дүгээр алхам руу шилжинэ.

Сэрэжа хэрэв алгоритм зогсох боломж нь хоосон биш тохиолдолд q тэмдэгт мөр дээр зөв ажилна гэж бодож байгаа. Гэхдээ хэрвээ алгоритм нь ямартай ч тэмдэгт мөр дээр эцэс төгсгөлгүйгээр ажилвал бид тухайн тэмдэгт мөр дээр буруу ажилаж байна гэж үзнэ.

Сэрэжа алгоритмаа шалгахыг хүсч байгаа. Тиймээс түүнд n үсгээс бүтсэн $s = s_1 s_2 ... s_n$ тэмдэгт мөр байгаа. Хүү m ширхэг тесттэй цуваа дамжуулна. i дугаар тестэнд, тэр алгоритмийн оролт руу $s_{l_i} s_{l_i} + 1... s_{r_i}$  ($1 ≤ l_i ≤ r_i ≤ n$) дэд тэмдэгт мөр явуулна. Даанч түүний алгоритмын ажилгаа нь хэтэрхий урт тул Сэрэжа та бүхнээс тусламж хүсчээ. Тест бүрд ($l_i$, $r_i$) байх ба энэ явуулсан тестэнд зөв буруу ажилах эсэхийг тодорхойл.

Оролт

Эхний мөрөнд $10^5$ хэтрэхгүй бүхэл n урттай хоосон биш тэмдэгт мөр өгөгдсөн. Энэ тэмдэгт мөр нь ‘x’,’y’,’z’ -ээс бүтнэ.

Дараагийн мөрөнд m бүхэл тоо ($1 ≤ m ≤ 10^5$) – тестийн тоо. Дараагийн $m$ мөрөнд тестүүд агуулагдана. $i$ дугаар мөрөнд $l_i$, $r_i$ ($1 ≤ l_i ≤ r_i ≤ n$) 2 хос тоо агуулна.

Гаралт

Тест бүрд алгоритм зөв ажилаж байвал “YES” бусад тохиолдолд “NO” гэж хэвлэнэ.

Орчуулсан: Gantushig

Жишээ тэстүүд

Оролт
zyxxxxxxyyz
5
5 5
1 3
1 11
1 4
3 6
Гаралт
YES
YES
NO
YES
NO

Тэмдэглэл

In the first example, in test one and two the algorithm will always be terminated in one step. In the fourth test you can get string "xzyx$" on which the algorithm will terminate. In all other tests the algorithm doesn't work correctly.

Сэтгэгдлүүдийг ачааллаж байна...