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: interview

Starter code:

Solutions:
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')

# cook your dish here
from bisect import bisect_left
for _ in range(int(input())):
 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')

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()


# cook your dish here
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
 # print(a)
 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)
  # print(b)
  for i in range(q):
   l, r = list(map(int, input().strip().split()))
   solve(b, n, l-1, r-1)


read()


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")
  else:
   if(L==1):
    if(count[R-3]>0):
     print("YES")
    else:
     print("NO")
   else:
    if(count[R-3]-count[L-2]>0):
     print("YES")
    else:
     print("NO")

# cook your dish here
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)
 # print(b)
 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")

# cook your dish here
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)
 # print(bi)
 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")


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")


for _ in range(int(input())):
 N,Q=map(int,input().split())
 S=input()
 Z=[0]*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')
  else:
   if Z[R-1]==Z[L]:
    print('NO')
   else:
    print('YES')

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')
  else:
   if Z[R-1]==Z[L]:
    print('NO')
   else:
    print('YES')

for _ in range(int(input())):
 N,Q=map(int,input().split())
 S=input()
 Z=[0]*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')
  else:
   if Z[R-1]==Z[L]:
    print('NO')
   else:
    print('YES')

for _ in range(int(input())):
 N, Q = map(int, input().split())
 S = input()
 Z = [0]*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')
  else:
   if Z[R-1] == Z[L]:
    print('NO')
   else:
    print('YES')

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)
 #list.append(0)
 sum=0
 ptr=0
 for i in s:
  # print(i)
  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 
 #print(list)            
 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 


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')
   



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")

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")




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]
 # print("counts = "+str(counts))
 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]
  # print("query = "+str((L,R))+" left, right = "+str((left,right)))
  if left < right:
   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)

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 collections import Counter
# class Node(object):
#     def __init__(self, start, end):
#         self.start = start
#         self.end = end
#         self.rich = None
#         self.left = None
#         self.right = None

# class SegmentTree(object):
#     def __init__(self):
#         self.root = None
 
#     def addToTree(self, l, r, string):
#         node = Node(l,r)

#         if r == len(string) - 1:
#             self.root = Node(l,r)
#             node = self.root
  
#         if r - l < 3:
#             node.rich = False
#             return node
#         else:
#             m = int((l+r)/2)
#             left, right = self.addToTree(l, m, string), self.addToTree(m+1, r,     string)
#             node.weight = any()
#             node.left = left
#             node.right = right
#             return node
  
# T = int(input())        
# for _ in range(T):
#     N, Q = map(int,input().split())
#     string = input()
#     ans = 1
#     for __ in range(Q):
#         L, R = map(int, input().split())
#         if R-L >= 2:
#             L -= 1
#             sub_str = string[L:R]
#             cnt = Counter(sub_str)
#             for value in cnt.values():
#                 if value > 2:
#                     ans = 0
#                     print('yes')
#                     break
#         else:
#             ans = 0
#             print('no')

#         if ans:
#             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 *
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)