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

یک رشته با طول $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