• محدودیت زمان: ۳ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

یک رشته‌ی باینری به نام $s$ داریم که فقط شامل کاراکترهای 0 و 1 است. هدف این است که به $q$ پرسش درباره این رشته پاسخ دهیم.

پرسش‌ها به دو نوع تقسیم می‌شوند:

1. جستجوی زیررشته: در این حالت، یک رشته‌ی باینری $t$ داده می‌شود و باید بررسی کنیم آیا این رشته به عنوان زیررشته‌ای متوالی در $s$ ظاهر شده است یا خیر.
2. تغییر کاراکتر: در این حالت، عدد صحیح $k$ داده می‌شود و باید کاراکتر $k$ام رشته $s$ را معکوس کنیم (یعنی 0 به 1 و 1 به 0 تبدیل شود).

ورودی

در سطر اول ورودی، دو عدد صحیح و مثبت $n$ و $q$ داده می‌شود که به‌ترتیب طول رشته‌ی $s$ و تعداد پرسش‌ها را نشان می‌دهد.

$$1 \leq n, q \leq 10^5$$

در سطر دوم ورودی، یک رشته از $n$ کاراکتر 0 یا 1 داده می‌شود که مقدار رشته‌ی $s$ را نشان می‌دهد.

در $q$ سطر بعدی، در هر سطر یکی از دو حالت زیر ورودی داده می‌شود.

• $\text{? } t$

که به‌جای $t$ رشته‌ی باینری داده می‌شود.

• $\text{! } k$

که به‌جای $k$ یک عدد صحیح داده می‌شود. $$1 \leq |t| \leq 10$$ $$1 \leq k \leq n$$

تضمین می‌شود حداقل یک پرسش از نوع اول داده شود.

خروجی

برای هر پرسش از نوع $?$ در صورت وجود رشته‌ی داده شده YES و در غیر این صورت NO چاپ کنید.

توجه کنید سیستم داوری نسبت به بزرگ و کوچک بودن حروف حساس است.

مثال‌ها

ورودی نمونه ۱

5 6
01010
? 111
? 010
? 000
! 3
? 111
? 110

خروجی نمونه ۱

NO
YES
NO
YES
YES

ورودی نمونه ۲

6 7
010110
? 01101
! 3
? 1111
! 4
? 01101
? 1
? 0

خروجی نمونه ۲

NO
YES
YES
YES
YES