يُعَدّ Vuong واحدًا من أعظم علماء الرياضيات على مرّ العصور! هوايته هي اكتشاف الخصائص الرياضية لكل شيء، وأحيانًا حتى للأشياء غير الموجودة! في يوم ميلاده، أهداه صديقه المبرمج سلسلة ثنائية $S$ طولها $n$. وبعد فترة وجيزة، اكتشف خاصيتين مثيرتين للاهتمام للغاية للسلسلة $S$:
$X(S)$: طول أقصر سلسلة ليست متتالية جزئية من $S$.
$Y(S)$: عدد السلاسل التي طولها $X(S)$ والتي ليست متتالية جزئية من $S$.
عندما رأى صديقه المبرمج مدى استمتاع Vuong باكتشاف هاتين الخاصيتين، فكّر أنه سيكون من الرائع تغيير السلسلة $S$ قليلًا أيضًا. سيقوم المبرمج بإجراء $q$ تعديلات بالتتابع على السلسلة $S$. كل تعديل يكون من أحد الأنواع التالية:
0 l r: تعيين $S_l,S_{l+1},\ldots,S_r$ إلى $0$.1 l r: تعيين $S_l,S_{l+1},\ldots,S_r$ إلى $1$.F l r: عكس $S_l,S_{l+1},\ldots,S_r$. أي إنه لكل $l\le i\le r$، إذا كان $S_i$ يساوي $0$ فعيّنه إلى $1$، وإلا فعيّنه إلى $0$.
وبالطبع، لكل نسخة معدّلة من $S$، كان Vuong سعيدًا أيضًا بإيجاد $X(S)$ و $Y(S)$، لأنه كان يوم ميلاده!
لكن اللغز لا يكتمل بدون إجابة. باعتبار السلسلة $S$ وقائمة التعديلات $q$ على السلسلة $S$، ساعد الصديق المبرمج في إيجاد $X(S)$ و $Y(S)$ لكل تعديل، حتى يتمكن من التحقق من نتيجة Vuong ومقارنتها بالإجابة.
نظرًا لأن الإجابة قد تكون كبيرة جدًا، يرجى طباعة الإجابة بباقي القسمة على $10^9+7$.
تكون السلسلة $a$ متتالية جزئية من السلسلة $b$ إذا كان بالإمكان الحصول على $a$ من $b$ بحذف عدة محارف (ربما صفر أو جميع المحارف). على سبيل المثال، bd و acd و b هي متتاليات جزئية من abcd، بينما da ليست كذلك.
الإدخال
يحتوي السطر الأول على عددين صحيحين $n,q$ ($1\le n,q\le100\,000$) — طول السلسلة $S$ وعدد التعديلات.
يحتوي السطر الثاني على السلسلة الثنائية $S$ التي طولها $n$.
يحتوي السطر $i$ من الأسطر الـ $q$ التالية على وصف العملية رقم $i$ بأحد الأشكال التالية:
0 l r($1\le l\le r\le n$): تعيين $S_l,S_{l+1},\ldots,S_r$ إلى $0$.1 l r($1\le l\le r\le n$): تعيين $S_l,S_{l+1},\ldots,S_r$ إلى $1$.F l r($1\le l\le r\le n$): عكس $S_l,S_{l+1},\ldots,S_r$.
الإخراج
لكل تعديل على $S$، اطبع في سطر واحد عددين صحيحين هما $X(S)$ و $Y(S)$ بباقي القسمة على $10^9+7$.
أمثلة
الإدخال 1
4 3 0110 0 2 3 1 3 4 F 2 3
الإخراج 1
1 1 2 1 3 4
ملاحظة
في المثال، السلسلة $S$ هي 0110، وهناك $q=3$ تعديلات على $S$.
يوضح الجدول التالي التعديلات التي أُجريت على $S$.
| الترتيب | التعديل | قيمة $S$ | $X(S)$ | $Y(S)$ |
|---|---|---|---|---|
| الابتدائي | 0110 |
$3$ | $5$ | |
| $1$ | 0 2 3 |
0000 |
$1$ | $1$ |
| $2$ | 1 3 4 |
0011 |
$2$ | $1$ |
| $3$ | F 2 3 |
0101 |
$3$ | $4$ |
بالنسبة إلى $S=$
0000، فإن $X(S)=1$ و $Y(S)=1$، لأنه توجد سلسلة واحدة فقط طولها $1$ ليست متتالية جزئية من $S$، وهي السلسلة1.بالنسبة إلى $S=$
0011، السلسلة10هي الأقصر، وهي السلسلة الوحيدة التي طولها $2$ وليست متتالية جزئية من $S$.بالنسبة إلى $S=$
0101، قائمة السلاسل ذات الطول الأقصر التي ليست متتاليات جزئية من $S$ هي{000, 100, 110, 111}.بالنسبة إلى السلسلة الابتدائية $S=$
0110، قائمة السلاسل ذات الطول الأقصر التي ليست متتاليات جزئية من $S$ هي{000, 001, 100, 101, 111}. لذلك $X(S)=3$ و $Y(S)=5$، ولكن لا يتوجب عليك طباعة هذين العددين.