A string with length $L$ is called rich if $L \ge 3$ and there is a character which occurs in this string strictly more than $L/2$ times.
You are given a string $S$ and you should answer $Q$ queries on this string. In each query, you are given a substring $S_L, S_{L+1}, \ldots, S_R$. Consider all substrings of this substring. You have to determine whether at least one of them is rich.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains two space-separated integers $N$ and $Q$.
- The second line contains a single string $S$ with length $N$.
- Each of the next $Q$ lines contains two space-separated integers $L$ and $R$ describing a query.

-----Output-----
For each query, print a single line containing the string "YES" if the given substring contains a rich substring or "NO" if it does not contain any rich substring.

-----Constraints-----
- $1 \le T \le 10$
- $1 \le N, Q \le 10^5$
- $1 \le L \le R \le N$
- $S$ contains only lowercase English letters

-----Example Input-----
1
10 2
helloworld
1 3
1 10

-----Example Output-----
NO
YES

Difficulty: HARD
Tags: String algorithms

Data structures

Range queries

Segment trees revisited
Skill types: Data structures

Range queries

Starter code:

Solutions:
from bisect import bisect_left
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	s = input()
	index = []
	for i in range(n - 2):
		dictt = {}
		for j in s[i:i + 3]:
			if j in dictt:
				dictt[j] += 1
			else:
				dictt[j] = 1
		if max(dictt.values()) >= 2:
			index += [i + 1]
	for __ in range(q):
		(l, r) = map(int, input().split())
		ind = bisect_left(index, l)
		if ind == len(index):
			print('NO')
		elif index[ind] + 2 <= r:
			print('YES')
		else:
			print('NO')


def precumpute(s, n):
	a = [0 for i in range(n)]
	b = [0 for i in range(n)]
	if n < 3:
		return b
	for i in range(n - 3, -1, -1):
		if s[i] == s[i + 1] or s[i + 1] == s[i + 2] or s[i] == s[i + 2]:
			a[i] = 1
	prev = -1
	for i in range(n - 1, -1, -1):
		if a[i] == 1:
			prev = i
		b[i] = prev
	return b

def solve(b, n, l, r):
	if n < 3:
		print('NO')
		return
	x = b[l]
	if x >= l and x <= r - 2:
		print('YES')
	else:
		print('NO')

def read():
	t = int(input())
	for j in range(t):
		(n, q) = list(map(int, input().strip().split()))
		s = input().strip()
		b = precumpute(s, n)
		for i in range(q):
			(l, r) = list(map(int, input().strip().split()))
			solve(b, n, l - 1, r - 1)
read()


for _ in range(int(input())):
	(N, Q) = map(int, input().split())
	S = input()
	Z = [0 for x in range(N)]
	LC = 0
	for I in range(2, N):
		if S[I - 2] == S[I - 1] or S[I - 2] == S[I] or S[I - 1] == S[I]:
			LC += 1
		Z[I] = LC
	for I in range(Q):
		(L, R) = map(int, input().split())
		F = 0
		if R - L < 2:
			print('NO')
		elif Z[R - 1] == Z[L]:
			print('NO')
		else:
			print('YES')


tc = int(input())
for _ in range(tc):
	(n, q) = map(int, input().split())
	s = input()
	girl = [0, 0]
	lastCount = 0
	for i in range(2, n):
		if s[i] == s[i - 1] or s[i] == s[i - 2] or s[i - 1] == s[i - 2]:
			lastCount += 1
		girl.append(lastCount)
	for _ in range(q):
		(l, r) = map(int, input().split())
		if r - l < 2:
			print('NO')
		else:
			diff = girl[r - 1] - girl[l]
			if diff > 0:
				print('YES')
			else:
				print('NO')


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	s = input()
	p = [0] * (n - 2)
	for j in range(n - 2):
		sub = set(list(s[j:j + 3]))
		if len(sub) <= 2:
			p[j] = 1
	for i in range(1, len(p)):
		p[i] += p[i - 1]
	p = [0] + p
	for _ in range(q):
		(l, r) = map(int, input().split())
		r -= 2
		if l > r:
			print('NO')
		elif p[r] - p[l - 1] > 0:
			print('YES')
		else:
			print('NO')


import collections as cl

def bins(a, k, n):
	(l, h) = (0, n - 1)
	while l <= h:
		mid = (l + h) // 2
		if a[mid] == k:
			return mid
		elif a[mid] > k:
			h = mid - 1
		else:
			l = mid + 1
	return l

def rich(a, n):
	res = []
	for i in range(0, len(a) - 2):
		if a[i] == a[i + 1] or a[i] == a[i + 2] or a[i + 1] == a[i + 2]:
			res += [i + 1]
	return res
t = int(input())
while t:
	t -= 1
	(n, q) = map(int, input().split())
	a = input().rstrip()
	res = rich(a, n)
	y = len(res)
	for i in range(q):
		(l, r) = map(int, input().split())
		if r - l <= 1:
			print('NO')
		else:
			ind = bins(res, l, y)
			if ind >= y:
				print('NO')
			elif res[ind] >= l and res[ind] <= r - 2:
				print('YES')
			else:
				print('NO')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	s = input()
	dp = [0] * (n - 2)
	for j in range(n - 2):
		st = set(list(s[j:j + 3]))
		if len(st) <= 2:
			dp[j] = 1
	for i in range(1, len(dp)):
		dp[i] += dp[i - 1]
	dp = [0] + dp
	for i in range(m):
		(u, v) = map(int, input().split())
		v -= 2
		if u > v:
			print('NO')
		elif dp[v] - dp[u - 1] > 0:
			print('YES')
		else:
			print('NO')


def compute_rich_substr(s):
	rich = [0 for _ in range(len(s) + 1)]
	for i in range(len(s) - 2):
		if s[i] == s[i + 1] or s[i] == s[i + 2] or s[i + 1] == s[i + 2]:
			rich[i + 1] = rich[i] + 1
		else:
			rich[i + 1] = rich[i]
	rich[len(s) - 1] = rich[len(s)] = rich[len(s) - 2]
	return rich
t = int(input())
for _ in range(t):
	(n, q) = list(map(int, input().strip().split()))
	s = input()
	rich = compute_rich_substr(s)
	for _ in range(q):
		(l, r) = list(map(int, input().strip().split()))
		if r - l + 1 < 3:
			print('NO')
		elif rich[r - 2] - rich[l - 1] > 0:
			print('YES')
		else:
			print('NO')


from itertools import accumulate
from collections import Counter

def is_dominant(ss):
	wc = Counter(ss)
	for i in wc.values():
		if i > 1:
			return True
	return False
t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split(' '))
	s = input()
	p = []
	if n > 2:
		for i in range(n - 2):
			ss = s[i:i + 3]
			if is_dominant(ss):
				val = 1
			else:
				val = 0
			p.append(val)
		p1 = list(accumulate(p))
	for i in range(q):
		(l, r) = map(int, input().split(' '))
		len = r - (l - 1)
		if n < 3 or len < 3:
			ans = 'NO'
		else:
			sum = p1[r - 3]
			if l > 1:
				sum -= p1[l - 2]
			if sum > 0:
				ans = 'YES'
			else:
				ans = 'NO'
		print(ans)


tt = int(input())
while tt:
	ans = [0] * 100001
	(n, q) = map(int, input().split())
	st = input()
	for i in range(2, n):
		if st[i] == st[i - 1] or st[i - 1] == st[i - 2] or st[i] == st[i - 2]:
			ans[i] = ans[i - 1] + 1
		else:
			ans[i] = ans[i - 1]
	for i in range(q):
		fi = 0
		(l, r) = map(int, input().split())
		if r - l < 2:
			print('NO')
		elif ans[r - 1] - ans[l]:
			print('YES')
		else:
			print('NO')
	tt -= 1


t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	s = input()
	if n < 3:
		for i in range(m):
			(a, b) = list(map(int, input().split()))
			print('NO')
	else:
		k = [s[0], s[1], s[2]]
		if k[0] == k[1] or k[1] == k[2] or k[0] == k[2]:
			c = 1
		else:
			c = 0
		ans = [0, c]
		for i in range(3, n):
			del k[0]
			k.append(s[i])
			if k[0] == k[1] or k[1] == k[2] or k[0] == k[2]:
				c += 1
			ans.append(c)
		for i in range(m):
			(a, b) = list(map(int, input().split()))
			if b - a < 2:
				print('NO')
				continue
			b -= 2
			a -= 1
			if ans[b] - ans[a] == 0:
				print('NO')
			else:
				print('YES')


T = int(input())
for test in range(T):
	(N, Q) = [int(v) for v in input().split()]
	S = input()
	start_points = [len(set(S[i:i + 3])) < 3 for i in range(N - 2)]
	if N < 3:
		count = []
	else:
		counts = [int(start_points[0])] + [0] * (N - 3)
		for i in range(1, N - 2):
			counts[i] = counts[i - 1] + start_points[i]
	for query in range(Q):
		(L, R) = [int(v) for v in input().split()]
		if L + 2 > R:
			print('NO')
			continue
		if L == 1:
			left = 0
		else:
			left = counts[L - 2]
		right = counts[R - 3]
		if left < right:
			print('YES')
		else:
			print('NO')


import sys
from math import ceil, floor
import bisect
RI = lambda : [int(x) for x in sys.stdin.readline().split()]
rw = lambda : sys.stdin.readline().strip()
for _ in range(int(input())):
	(n, q) = RI()
	st = input()
	bi = []
	for i in range(len(st) - 2):
		if st[i] == st[i + 1] or st[i] == st[i + 2] or st[i + 1] == st[i + 2]:
			bi.append(i)
	for qq in range(q):
		(a, b) = RI()
		a -= 1
		b -= 1
		pos = bisect.bisect_right(bi, a - 1)
		if pos == len(bi) or bi[pos] + 2 > b:
			print('NO')
		else:
			print('YES')


t = int(input())
for _ in range(t):
	(n, q) = [int(p) for p in input().split()]
	s = input()
	l = [0] * n
	if n > 2:
		for i in range(n - 2):
			v1 = s[i]
			v2 = s[i + 1]
			v3 = s[i + 2]
			if v1 == v2 or v2 == v3 or v1 == v3:
				l[i] = 1
			else:
				l[i] = 0
		li = [0] * n
		val = 0
		for i in range(n):
			val += l[i]
			li[i] = val
		for i in range(q):
			(ll, hl) = [int(p) for p in input().split()]
			if hl - ll + 1 >= 3:
				if ll > 1:
					ans = li[hl - 3] - li[ll - 2]
				else:
					ans = li[hl - 3]
			else:
				ans = 0
			if ans < 1:
				print('NO')
			else:
				print('YES')
	else:
		for i in range(q):
			(ll, hl) = [int(p) for p in input().split()]
			print('NO')


R = lambda : map(int, input().split())
for _ in range(int(input())):
	(n, q) = R()
	s = input()
	L = []
	for i in range(n - 2):
		if s[i] == s[i + 1] or s[i] == s[i + 2] or s[i + 1] == s[i + 2]:
			L.append(1)
		else:
			L.append(0)
	for i in range(1, len(L)):
		L[i] += L[i - 1]
	L = [0] + L
	for j in range(q):
		(l, r) = R()
		r -= 2
		if l > r:
			print('NO')
		elif L[r] - L[l - 1] > 0:
			print('YES')
		else:
			print('NO')


from bisect import *

def fun(s):
	s = list(s)
	s.sort()
	if s[0] == s[1] or s[1] == s[2]:
		return True
	return False
for z in range(int(input())):
	(n, q) = map(int, input().split())
	s = input()
	lis = [0] * n
	for i in range(3, n + 1):
		if fun(s[i - 3:i]):
			lis[i - 1] = 1
	a = []
	for i in range(n):
		if lis[i] == 1:
			a.append(i + 1)
	for y in range(q):
		(l, r) = map(int, input().split())
		x = bisect_left(a, l + 2)
		if x == len(a) or r - l < 2:
			print('NO')
		elif a[x] <= r:
			print('YES')
		else:
			print('NO')


for t in range(int(input())):
	(n, q) = map(int, input().split())
	st = input()
	ans = [0 for i in range(n)]
	for i in range(n - 2):
		if st[i] == st[i + 1] or st[i] == st[i + 2] or st[i + 1] == st[i + 2]:
			ans[i] = 1
	prefix = [0 for i in range(n + 1)]
	for i in range(n):
		prefix[i + 1] = prefix[i] + ans[i]
	for i in range(q):
		(l, r) = map(int, input().split())
		if r - l < 2:
			print('NO')
		elif prefix[r - 2] - prefix[l - 1] > 0:
			print('YES')
		else:
			print('NO')


t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	s = input()
	l = [0] * (n - 1)
	for i in range(n - 2):
		(a, b, c) = (s[i], s[i + 1], s[i + 2])
		if len(set([a, b, c])) < 3:
			l[i] = l[i - 1] + 1
		else:
			l[i] = l[i - 1]
	for i in range(q):
		(left, right) = map(int, input().split())
		left -= 1
		right -= 1
		if right - left + 1 < 3:
			print('NO')
			continue
		if l[right - 2] - l[left - 1] > 0:
			print('YES')
		else:
			print('NO')


from bisect import *

def solve(arr, n, l, r):
	i = bisect_left(arr, l - 1)
	if i >= n:
		print('NO')
		return
	if arr[i] + 2 <= r - 1:
		print('YES')
	else:
		print('NO')
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	arr = [i for i in input()]
	s_set = list()
	for i in range(n - 2):
		if arr[i] == arr[i + 1] or arr[i + 1] == arr[i + 2] or arr[i] == arr[i + 2]:
			s_set.append(i)
	n = len(s_set)
	for i in range(q):
		(l, r) = map(int, input().split())
		solve(s_set, n, l, r)


t = int(input())
while t > 0:
	(x, q) = input().split()
	x = int(x)
	q = int(q)
	s = input()
	list = []
	list.append(0)
	list.append(0)
	sum = 0
	ptr = 0
	for i in s:
		if ptr + 2 > len(s) - 1:
			break
		else:
			a = s[ptr]
			b = s[ptr + 1]
			c = s[ptr + 2]
			if (a == b) | (b == c) | (a == c):
				sum += 1
			list.append(sum)
			ptr += 1
	while q > 0:
		(l, r) = input().split()
		l = int(l)
		r = int(r)
		if r - l < 2:
			print('NO')
		else:
			res = list[r - 1] - list[l]
			if res > 0:
				print('YES')
			else:
				print('NO')
		q -= 1
	t -= 1


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	s = input()
	repeats = [0 for i in range(n)]
	for i in range(n - 2):
		if len(set(s[i:i + 3])) <= 2:
			repeats[i] = 1
	carr = [0 for i in range(n + 1)]
	le = 0
	for i in range(n):
		carr[i + 1] = repeats[i] + le
		le = carr[i + 1]
	for i in range(q):
		(l, r) = map(int, input().split())
		if r - l >= 2:
			if carr[r - 2] - carr[l - 1] == 0:
				print('NO')
			else:
				print('YES')
		else:
			print('NO')


from bisect import *
t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	s = input()
	l = []
	for i in range(n - 2):
		(a, b, c) = (s[i], s[i + 1], s[i + 2])
		if len(set([a, b, c])) < 3:
			l.append(i)
	for i in range(q):
		(left, right) = map(int, input().split())
		left -= 1
		right -= 1
		if right - left + 1 < 3:
			print('NO')
			continue
		p1 = bisect_left(l, left)
		if p1 != len(l) and l[p1] <= right - 2:
			print('YES')
		else:
			print('NO')


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	a = input()
	b = [0]
	for i in range(n - 2):
		if a[i] == a[i + 1] or a[i + 1] == a[i + 2] or a[i] == a[i + 2]:
			b.append(b[-1] + 1)
		else:
			b.append(b[-1] + 0)
	for i in range(q):
		(l, r) = map(int, input().split())
		if r - l < 2:
			print('NO')
		elif b[r - 2] - b[l - 1] > 0:
			print('YES')
		else:
			print('NO')


T = int(input())
for _ in range(T):
	(N, Q) = [int(b) for b in input().split()]
	S = input()
	b = [0, 0]
	l = 0
	for i in range(len(S) - 2):
		a = S[i:i + 3]
		if a[0] == a[1] or a[0] == a[2] or a[1] == a[2]:
			l += 1
		b.append(l)
	for i in range(Q):
		(L, R) = [int(b) for b in input().split()]
		if R - L < 2:
			print('NO')
			continue
		if b[R - 1] - b[L] > 0:
			print('YES')
		else:
			print('NO')


for t in range(int(input())):
	(n, q) = map(int, input().split())
	s = input()
	index = [-1] * n
	temp = -1
	for i in range(n - 2):
		if s[i] == s[i + 1] or s[i] == s[i + 2] or s[i + 2] == s[i + 1]:
			temp = i
		index[i + 2] = temp
	for Q in range(q):
		(l, r) = map(int, input().split())
		if index[r - 1] >= l - 1:
			print('YES')
		else:
			print('NO')


def isvalid(s):
	if s[0] == s[1] or s[1] == s[2] or s[0] == s[2]:
		return 1
	return 0
t = int(input())
for you in range(t):
	l = input().split()
	n = int(l[0])
	q = int(l[1])
	s = input()
	count = [0 for i in range(n - 2)]
	fre = 0
	for i in range(n - 2):
		if isvalid(s[i:i + 3]):
			fre += 1
		count[i] = fre
	for i in range(q):
		l = input().split()
		L = int(l[0])
		R = int(l[1])
		if R - L + 1 < 3:
			print('NO')
		elif L == 1:
			if count[R - 3] > 0:
				print('YES')
			else:
				print('NO')
		elif count[R - 3] - count[L - 2] > 0:
			print('YES')
		else:
			print('NO')


def getCumulative(string):
	cumulative = [0]
	for i in range(len(string) - 2):
		nextVal = 1 if checkThreeCharsForward(i, string) else 0
		cumulative.append(cumulative[-1] + nextVal)
	return cumulative

def checkThreeCharsForward(i, s):
	return s[i] == s[i + 1] or s[i] == s[i + 2] or s[i + 1] == s[i + 2]

def isRich(left, right, cumulative):
	return right - left >= 2 and cumulative[right - 2] - cumulative[left - 1] > 0
for _ in range(int(input())):
	(_, numQueries) = [int(i) for i in input().split()]
	cumulative = getCumulative(input())
	for _ in range(numQueries):
		(left, right) = [int(i) for i in input().split()]
		print('YES' if isRich(left, right, cumulative) else 'NO')


def abc(k, a, b):
	i = 0
	j = len(k) - 1
	while i <= j:
		mid = i + (j - i) // 2
		if k[mid] > b:
			j = mid - 1
		elif k[mid] < a:
			i = mid + 1
		else:
			return True
	return False
t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	s = input()
	if n <= 2:
		for i in range(q):
			(a, b) = map(int, input().split())
			print('NO')
		continue
	k = []
	for i in range(n - 2):
		a = s[i]
		b = s[i + 1]
		c = s[i + 2]
		if a == b or b == c or a == c:
			k.append(i)
	for i in range(q):
		(a, b) = map(int, input().split())
		a -= 1
		b -= 1
		if b - a < 2:
			print('NO')
		else:
			flag = abc(k, a, b - 2)
			if flag:
				print('YES')
			else:
				print('NO')


from bisect import bisect_left
t = int(input())
for z in range(t):
	ar = input().split()
	(n, q) = (int(ar[0]), int(ar[1]))
	s = input()
	a2 = []
	a3 = []
	for i in range(n):
		if i < n - 1 and s[i] == s[i + 1]:
			a2.append(i)
		if i < n - 2 and s[i] == s[i + 2]:
			a3.append(i)
	for i in range(q):
		ar = input().split()
		(l, r) = (int(ar[0]) - 1, int(ar[1]) - 1)
		b2 = bisect_left(a2, l)
		b3 = bisect_left(a3, l)
		if r - l >= 2 and (b2 < len(a2) and a2[b2] + 1 <= r or (b3 < len(a3) and a3[b3] + 2 <= r)):
			print('YES')
		else:
			print('NO')


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	s = input()
	c = 0
	a = [0] * n
	for i in range(2, n):
		if s[i] == s[i - 1] or s[i] == s[i - 2] or s[i - 1] == s[i - 2]:
			c += 1
		a[i] = c
	for j in range(q):
		(d, b) = map(int, input().split())
		if b - d < 2:
			print('NO')
		elif a[b - 1] > a[d]:
			print('YES')
		else:
			print('NO')


from bisect import *
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	l = list(input())
	s = []
	for i in range(n - 2):
		if l[i] == l[i + 1] or l[i + 1] == l[i + 2] or l[i] == l[i + 2]:
			s.append(i)
	n = len(s)
	for i in range(q):
		(l, r) = map(int, input().split())
		ind = bisect_left(s, l - 1)
		if ind >= n:
			print('NO')
			continue
		if s[ind] + 2 <= r - 1:
			print('YES')
		else:
			print('NO')


t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	s = input()
	dp = [0] * (n + 1)
	for i in range(n - 2):
		p = s[i:i + 3]
		if p.count(p[0]) >= 2 or p.count(p[1]) >= 2:
			dp[i + 1] = dp[i] + 1
		else:
			dp[i + 1] = dp[i]
	for _ in range(q):
		(l, r) = map(int, input().split())
		if n < 3 or r - l < 2:
			print('NO')
			continue
		if dp[r - 2] - dp[l - 1] > 0:
			print('YES')
		else:
			print('NO')


from bisect import bisect_left as bl
t = int(input())
for i in range(t):
	(n, q) = map(int, input().split())
	s = input()
	c = []
	for i in range(len(s) - 2):
		if s[i] == s[i + 1] or s[i + 1] == s[i + 2] or s[i] == s[i + 2]:
			c.append(i + 1)
	for i in range(q):
		(l, r) = map(int, input().split())
		x = bl(c, l)
		if len(c) == 0 or r - l < 2 or x == len(c):
			print('NO')
		else:
			st = c[x]
			if st + 2 <= r:
				print('YES')
			else:
				print('NO')


import math
import sys
from heapq import heappop
from heapq import heappush
from heapq import heapify
from bisect import insort
from sys import stdin, stdout
from collections import defaultdict
inp = lambda : int(stdin.readline())
sip = lambda : input()
mulip = lambda : map(int, input().split())
lst = lambda : list(map(int, stdin.readline().split()))
slst = lambda : list(sip())
arr2d = lambda x: [[int(j) for j in input().split()] for i in range(x)]
odds = lambda l: len(list(filter(lambda x: x % 2 != 0, l)))
evens = lambda l: len(list(filter(lambda x: x % 2 == 0, l)))
mod = pow(10, 9) + 7
for _ in range(int(input())):
	(N, Q) = mulip()
	S = list(input())
	l = [0, 0]
	cnt = 0
	j = 0
	for i in range(3, N + 1):
		temp = S[j:i]
		d = defaultdict(int)
		f = 0
		for i in temp:
			d[i] += 1
		for i in d:
			if d[i] >= 2:
				cnt += 1
				f = 1
		if f == 1:
			l.append(1)
		else:
			l.append(0)
		j += 1
	M = [0] * (N + 1)
	for i in range(1, N + 1):
		M[i] = M[i - 1] + l[i - 1]
	for i in range(Q):
		(l1, r) = mulip()
		if r - l1 == 0:
			ans = 0
		else:
			ans = M[r] - M[l1 + 1]
		if ans > 0:
			print('YES')
		else:
			print('NO')


from bisect import *

def sub_string(temp, n, l, r):
	index = bisect_left(temp, l - 1)
	if index >= n:
		print('NO')
		return
	if temp[index] + 2 <= r - 1:
		print('YES')
	else:
		print('NO')
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	s = [x for x in input()]
	temp = []
	for i in range(n - 2):
		if s[i] == s[i + 1] or s[i + 1] == s[i + 2] or s[i] == s[i + 2]:
			temp.append(i)
	n = len(temp)
	for i in range(q):
		(l, r) = map(int, input().split())
		sub_string(temp, n, l, r)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	s = input()
	prefix = [0] * n
	for i in range(2, n):
		prefix[i] = prefix[i - 1]
		if s[i] == s[i - 1] or s[i - 1] == s[i - 2] or s[i] == s[i - 2]:
			prefix[i] += 1
	for i in range(q):
		(l, r) = map(int, input().split())
		if r - l + 1 < 3:
			print('NO')
		elif prefix[r - 1] - prefix[l] > 0:
			print('YES')
		else:
			print('NO')


from bisect import bisect_left
for _ in range(int(input())):
	(n, q) = [int(i) for i in input().split()]
	s = input()
	dp = []
	dp1 = []
	for i in range(n - 2):
		if s[i] == s[i + 1]:
			dp.append([i, 1])
			dp1.append(i)
		if s[i] == s[i + 2]:
			dp.append([i, 2])
			dp1.append(i)
	if s[n - 2] == s[n - 1]:
		dp.append([n - 2, 1])
	for i in range(q):
		(l, r) = [int(i) for i in input().split()]
		l -= 1
		r -= 1
		flag = 0
		pos = bisect_left(dp1, l)
		if pos >= len(dp):
			print('NO')
			continue
		if dp[pos][1] == 2:
			if r >= dp[pos][0] + 2:
				flag = 1
		elif dp[pos][1] == 1:
			if r >= dp[pos][0] + 2:
				flag = 1
			elif r == dp[pos][0] + 1 and l < dp[pos][0]:
				flag = 1
		if flag:
			print('YES')
		else:
			print('NO')


t = int(input())
for i in range(t):
	nq = input().split(' ')
	(n, q) = (int(nq[0]), int(nq[1]))
	s = input()
	a = [0 for i in range(len(s))]
	b = [0 for i in range(len(s))]
	for j in range(len(s) - 2):
		if s[j] == s[j + 1] or s[j] == s[j + 2] or s[j + 1] == s[j + 2]:
			a[j] = 1
	prev = -1
	for j in range(len(s) - 1, -1, -1):
		if a[j] != 0:
			prev = j
		b[j] = prev
	for j in range(q):
		ab = input().split(' ')
		(x, y) = (int(ab[0]) - 1, int(ab[1]) - 1)
		if b[x] == -1:
			print('NO')
			continue
		if b[x] + 2 <= y:
			print('YES')
		else:
			print('NO')


for tea in range(int(input())):
	(n, q) = map(int, input().split())
	s = list(input())
	if n <= 2:
		for qq in range(q):
			input()
			print('NO')
		continue
	gud = []
	for i in range(n - 2):
		if len(set([s[i], s[i + 1], s[i + 2]])) < 3:
			gud.append(i)
	stuff = dict()
	ind = 0
	for i in range(n):
		stuff[i] = ind
		if ind < len(gud) and i >= gud[ind]:
			ind += 1
	for qq in range(q):
		(l, r) = [int(x) - 1 for x in input().split()]
		r -= 2
		if l > r:
			print('NO')
			continue
		if stuff[l] == stuff[r + 1]:
			print('NO')
		else:
			print('YES')


T = int(input())
for k in range(T):
	(N, Q) = map(int, input().split())
	s = input()
	l = [0 for i in range(N)]
	p = -1
	for i in range(2, N):
		if s[i] == s[i - 1] or s[i - 1] == s[i - 2] or s[i] == s[i - 2]:
			p = i
			l[i] = p + 1
		else:
			l[i] = p + 1
	for _ in range(Q):
		(a, b) = map(int, input().split())
		flag = 0
		if l[b - 1] - 2 >= a:
			flag = 1
		if flag:
			print('YES')
		else:
			print('NO')


import bisect

def solve(s_set, L, R):
	pos = bisect.bisect_left(s_set, L)
	if pos >= len(s_set):
		print('NO')
		return
	if s_set[pos] + 2 <= R:
		print('YES')
	else:
		print('NO')
for _ in range(int(input())):
	(N, Q) = map(int, input().split(' '))
	given = [i for i in input()]
	s_set = []
	for i in range(len(given) - 3 + 1):
		if given[i] == given[i + 1] or given[i] == given[i + 2] or given[i + 1] == given[i + 2]:
			s_set.append(i + 1)
	for i in range(Q):
		(L, R) = map(int, input().split(' '))
		solve(s_set, L, R)


n = int(input())
for i in range(0, n):
	p = input().rstrip().split(' ')
	s = input().rstrip()
	x = list(s)
	q = []
	w = []
	S = []
	D = []
	if len(x) < 3:
		for j in range(0, int(p[1])):
			G = input().rstrip().split(' ')
			print('NO')
	else:
		l = [0] * 26
		for j in range(0, 3):
			A = ord(x[j]) - 97
			l[A] += 1
		for j in range(0, 26):
			if l[j] > 1:
				q.append(1)
				break
		for j in range(1, len(x) - 3 + 1):
			A = ord(x[j - 1]) - 97
			l[A] -= 1
			B = ord(x[j + 3 - 1]) - 97
			l[B] += 1
			for k in range(0, 26):
				if l[k] > 1:
					q.append(j + 1)
					break
		for j in range(0, int(p[1])):
			G = input().rstrip().split(' ')
			if int(G[1]) - int(G[0]) + 1 < 3:
				print('NO')
			else:
				I = 0
				J = len(q) - 1
				H = 0
				while I <= J:
					m = (I + J) // 2
					if int(q[m]) >= int(G[0]) and int(q[m]) + 2 <= int(G[1]):
						H = 1
						break
					elif int(q[m]) < int(G[0]):
						I = m + 1
					else:
						J = m - 1
				if H == 0:
					print('NO')
				else:
					print('YES')


def nlebs(a, l, r, x):
	ans = -1
	if x > a[-1]:
		return -1
	while l <= r:
		mid = int((l + r) / 2)
		if a[mid] == x:
			return mid
		elif a[mid] > x:
			ans = mid
			r = mid - 1
		else:
			l = mid + 1
	return ans
from bisect import bisect_left
from bisect import bisect_right

def nsebs(a, l, r, x):
	ans = -1
	if x < a[0]:
		return -1
	while l <= r:
		mid = int((l + r) / 2)
		if a[mid] == x:
			return mid
		elif a[mid] > x:
			r = mid - 1
		else:
			ans = mid
			l = mid + 1
	return ans
import collections
t = int(input())
for i in range(t):
	(n, m) = [int(x) for x in input().split()]
	s = input()
	arr = []
	for i in range(n - 2):
		p = s[i:i + 3]
		if p[1] == p[0] or p[1] == p[2] or p[0] == p[2]:
			arr.append((i + 1, i + 3))
	first = []
	second = []
	l = len(arr)
	for i in arr:
		first.append(i[0])
		second.append(i[1])
	for i in range(m):
		(p, q) = [int(x) for x in input().split()]
		if l == 0:
			print('NO')
			continue
		if p > first[-1] or q < second[0]:
			print('NO')
			continue
		qi = bisect_left(second, q)
		if qi == l:
			qi = l - 1
		elif second[qi] != q:
			qi -= 1
		pi = bisect_left(first, p)
		if pi <= qi:
			print('YES')
		else:
			print('NO')


t = int(input())
for _ in range(t):
	(n, q) = [int(i) for i in input().split()]
	string = input()
	richBinaryList = [False for _ in range(len(string))]
	leastRightList = [0 for _ in range(len(string))]
	for i in range(len(string) - 2):
		first = string[i]
		second = string[i + 1]
		third = string[i + 2]
		if first == second or first == third or second == third:
			richBinaryList[i] = True
	lastRich = None
	for i in range(len(string) - 1, -1, -1):
		if richBinaryList[i]:
			lastRich = i
		if lastRich is None:
			leastRight = None
		else:
			leastRight = lastRich + 2
		leastRightList[i] = leastRight
	for _ in range(q):
		(l, r) = [int(i) - 1 for i in input().split()]
		length = r - l + 1
		if length < 3:
			print('NO')
		elif leastRightList[l] is None:
			print('NO')
		elif leastRightList[l] <= r:
			print('YES')
		else:
			print('NO')


from bisect import bisect_left
for _ in range(int(input())):
	(nota, quota) = [int(i) for i in input().split()]
	s = input()
	dope = []
	dope1 = []
	for i in range(nota - 2):
		if s[i] == s[i + 1]:
			dope.append([i, 1])
			dope1.append(i)
		if s[i] == s[i + 2]:
			dope.append([i, 2])
			dope1.append(i)
	if s[nota - 2] == s[nota - 1]:
		dope.append([nota - 2, 1])
	for i in range(quota):
		(l, r) = [int(i) for i in input().split()]
		l -= 1
		r -= 1
		flag = 0
		pos = bisect_left(dope1, l)
		if pos >= len(dope):
			print('NO')
			continue
		if dope[pos][1] == 2:
			if r >= dope[pos][0] + 2:
				flag = 1
		elif dope[pos][1] == 1:
			if r >= dope[pos][0] + 2:
				flag = 1
			elif r == dope[pos][0] + 1 and l < dope[pos][0]:
				flag = 1
		if flag:
			print('YES')
		else:
			print('NO')


__author__ = 'Ronald Kaiser'
__email__ = 'raios dot catodicos at gmail dot com'
for _ in range(int(input())):
	(N, Q) = list(map(int, input().split()))
	S = input()
	dp = [-1 for i in range(len(S))]
	for i in range(len(S) - 3, -1, -1):
		if len(set(S[i:i + 3])) <= 2:
			dp[i] = i + 2
		elif dp[i + 1] != -1:
			dp[i] = dp[i + 1]
	for _ in range(Q):
		(L, R) = list(map(int, input().split()))
		L -= 1
		R -= 1
		if dp[L] != -1 and dp[L] <= R:
			print('YES')
		else:
			print('NO')


import re
for _ in range(int(input())):
	(N, Q) = map(int, input().split())
	S = input()
	is_rich = [bool(re.match('(?:.?(.)\\1)|(?:(.).\\2)', S[i:i + 3])) for i in range(N - 2)]
	next_rich = []
	i = 0
	while len(next_rich) < N - 2:
		while i < len(next_rich) or (i < N - 2 and (not is_rich[i])):
			i += 1
		next_rich.append(i)
	next_rich.append(N)
	next_rich.append(N)
	for i in range(Q):
		(L, R) = map(int, input().split())
		print(['NO', 'YES'][next_rich[L - 1] < R - 2])


from itertools import accumulate
t = int(input())
while t:
	(n, q) = [int(x) for x in input().split()]
	s = input()
	if n < 3:
		for _ in range(q):
			(l, r) = [int(x) for x in input().split()]
			print('NO')
	else:
		temp = [0] * (n - 2)
		for i in range(n - 2):
			if s[i] == s[i + 1] or s[i + 2] == s[i + 1] or s[i] == s[i + 2]:
				temp[i] = 1
		temp = list(accumulate(temp))
		for _ in range(q):
			(l, r) = [int(x) for x in input().split()]
			if r - l < 2:
				print('NO')
				continue
			r -= 3
			if l == 1:
				if temp[r] > 0:
					print('YES')
				else:
					print('NO')
			elif temp[r] - temp[l - 2] > 0:
				print('YES')
			else:
				print('NO')
	t -= 1


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	st = input()
	freq = [0]
	count = 0
	for i in range(n - 2):
		if len(set(st[i:i + 3])) < 3:
			count += 1
		freq.append(count)
	for _ in range(q):
		(l, r) = map(int, input().split())
		if r - l < 2:
			print('NO')
			continue
		if r - l == 2:
			if freq[l] - freq[l - 1] > 0:
				print('YES')
			else:
				print('NO')
			continue
		if freq[r - 2] - freq[l] > 0 or freq[l] - freq[l - 1] > 0:
			print('YES')
		else:
			print('NO')


def list_inp():
	return [int(val.strip()) for val in input().split()]

def main():
	T = list_inp()[0]
	while T:
		T -= 1
		(N, Q) = list_inp()
		inp_str = input().strip()
		good_subs_3 = [0 for _ in range(N)]
		for i in range(len(inp_str) - 3 + 1):
			if i > 0:
				good_subs_3[i] = good_subs_3[i - 1]
			if inp_str[i] == inp_str[i + 1] or inp_str[i] == inp_str[i + 2] or inp_str[i + 1] == inp_str[i + 2]:
				good_subs_3[i] += 1
		while Q:
			Q -= 1
			(l, r) = list_inp()
			l -= 1
			r -= 1
			if l > r - 2:
				print('NO')
			else:
				good_count = good_subs_3[r - 2]
				if l > 0:
					good_count -= good_subs_3[l - 1]
				if good_count > 0:
					print('YES')
				else:
					print('NO')
main()


def isvalid(string):
	if string.count(string[0]) == 2 or string[1] == string[2]:
		return True
	return False
for _ in range(int(input())):
	(N, Q) = list(map(int, input().split()))
	s = input()
	if N <= 2:
		for i in range(Q):
			x = input()
			print('NO')
		continue
	if N == 3:
		x = isvalid(s)
		for i in range(Q):
			(a, b) = list(map(int, input().split()))
			if x and a == 1 and (b == 3):
				print('YES')
			else:
				print('NO')
		continue
	valid3s = ['No', 'No']
	dp = []
	for i in range(N - 2):
		if isvalid(s[i:i + 3]):
			valid3s.append('Yes')
		else:
			valid3s.append('No')
	i = 2
	while i < N:
		j = 1
		while i < N and valid3s[i] != 'Yes':
			i += 1
			j += 1
		for tmp in range(j):
			dp.append(i)
		i += 1
	for i in range(Q):
		(L, R) = list(map(int, input().split()))
		L -= 1
		R -= 1
		if L >= len(dp):
			print('NO')
		elif dp[L] > R:
			print('NO')
		else:
			print('YES')


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	s = list(input())
	t = 0
	li = []
	for i in range(n - 2):
		li.append(t)
		if s[i] == s[i + 1] or s[i] == s[i + 2] or s[i + 1] == s[i + 2]:
			t += 1
	li.append(t)
	li.append(0)
	li.append(0)
	for _ in range(q):
		(l, r) = map(int, input().split())
		l -= 1
		r -= 1
		if r - l >= 2:
			if li[r - 1] - li[l] > 0:
				print('YES')
			else:
				print('NO')
		else:
			print('NO')


import bisect

def solve(arr, size, Left, Right):
	i = bisect.bisect_left(arr, Left - 1)
	if i >= size:
		print('NO')
		return
	if arr[i] + 2 <= Right - 1:
		print('YES')
	else:
		print('NO')
for i in range(int(input())):
	(N, Q) = map(int, input().split())
	s = [i for i in input()]
	ss = []
	for i in range(0, len(s) - 2):
		if s[i] == s[i + 1] or s[i] == s[i + 2] or s[i + 1] == s[i + 2]:
			ss.append(i)
	size = len(ss)
	for i in range(Q):
		(L, R) = map(int, input().split())
		solve(ss, size, L, R)


t = int(input())
while t:
	(n, q) = map(int, input().split())
	s = input()
	lol = 0
	ll = [0] * n
	for i in range(n - 2):
		li = []
		li.append(s[i])
		li.append(s[i + 1])
		li.append(s[i + 2])
		li.sort()
		if li[0] == li[1] or li[1] == li[2]:
			lol = 1
			ll[i + 2] += 1
	for i in range(1, n):
		ll[i] = ll[i - 1] + ll[i]
	for _ in range(q):
		(l, r) = map(int, input().split())
		l -= 1
		r -= 1
		if l + 2 < n and ll[l + 1] - ll[l] == 1 and (ll[l + 1] == ll[r]) and (r - l + 1 >= 3):
			print('NO')
		elif ll[r] - ll[l] and r - l + 1 >= 3:
			print('YES')
		else:
			print('NO')
	t -= 1