• محدودیت زمان: ۶ ثانیه (برای تمامی زبان‌های برنامه‌نویسی)
• محدودیت حافظه: ۵۱۲ مگابایت (برای تمامی زبان‌های برنامه‌نویسی)

---

یک رشته با طول \(L\) را خفن می‌نامیم اگر \(L \ge 3\) باشد و یک کاراکتر وجود داشته باشد که اکیداً بیش از \(L/2\) بار در این رشته ظاهر شود.

رشته‌ای به نام \(S\) به شما داده شده است و شما باید \(Q\) پرسش را در مورد این رشته پاسخ دهید. در هر پرسش، یک زیررشته‌ی پیوسته \(S_L, S_{L+1}, \ldots, S_R\,\) به شما داده می‌شود. تمام زیررشته‌های پیوسته‌ی این زیررشته را در نظر بگیرید. شما باید تعیین کنید که آیا حداقل یکی از آن‌ها خفن است یا خیر.

ورودی

• اولین خط ورودی شامل یک عدد صحیح \(T\) است که تعداد سناریوها را نشان می‌دهد. سپس توضیحات \(T\) سناریو به دنبال آن می‌آید.
• اولین خط هر سناریو شامل دو عدد صحیح جداشده با فاصله، \(N\) و \(Q\) است (اول \(N\) می‌آید و سپس \(Q\)).
• خط دوم شامل یک رشته‌ی \(S\) با طول \(N\) است.
• هر یک از \(Q\) خط بعدی شامل دو عدد صحیح جداشده با فاصله‌ی \(L\) و \(R\) است که یک پرسش را توصیف می‌کند.

خروجی

برای هر پرسش، یک خط شامل YES چاپ کنید اگر زیررشته‌ی داده‌شده شامل حداقل یک زیررشته‌ی خفن باشد و یا NO اگر هیچ زیررشته‌ی خفنی در آن وجود نداشته باشد.

محدودیت‌ها

• \(1 \leq T \leq 10\)
• \(1 \leq N, Q \leq 10^5\)
• \(1 \leq L \leq R \leq N\)
• رشته‌ی \(S\) فقط شامل حروف کوچک انگلیسی است.

مثال

ورودی نمونه ۱

1
10 2
helloworld
1 3
1 10

خروجی نمونه ۱

NO
YES