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$, אך אין צורך להדפיס את שני המספרים הללו.