Vuong — барлық уақыттағы ең ұлы математиктердің бірі! Оның сүйікті ісі — барлық нәрсенің, тіпті кейде жоқ нәрселердің де математикалық қасиеттерін табу! Туған күнінде оның бағдарламашы досы оған ұзындығы $n$ болатын $S$ екілік жолын сыйлады. Біраз уақыттан кейін ол $S$ жолының өте қызықты екі қасиетін тапты:
$X(S)$: $S$ жолының ішкі тізбегі болмайтын ең қысқа жолдың ұзындығы.
$Y(S)$: ұзындығы $X(S)$ болатын және $S$ жолының ішкі тізбегі болмайтын жолдардың саны.
Vuong-тың осы екі қасиетті табудан ләззат алғанын көрген бағдарламашы досы $S$ жолын да аздап өзгертіп отыру керемет болар еді деп ойлады. Бағдарламашы $S$ жолына тізбектей $q$ өзгеріс енгізеді. Әрбір өзгеріс келесі түрлердің біріне жатады:
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$ жолы және $S$ жолына жасалатын $q$ өзгерістер тізімі берілген. Бағдарламашы досы Vuong-тың нәтижесін жауаппен тексере алуы үшін, оған әрбір өзгерістен кейінгі $X(S)$ пен $Y(S)$ мәндерін табуға көмектесіңіз.
Жауап өте үлкен болуы мүмкін болғандықтан, жауапты $10^9+7$ модулі бойынша шығарыңыз.
Егер $a$ жолын $b$ жолынан бірнеше (мүмкін нөл немесе барлық) таңбаны өшіру арқылы алуға болса, $a$ жолы $b$ жолының ішкі тізбегі деп аталады. Мысалы, bd, acd, b жолдары abcd жолының ішкі тізбектері болып табылады, ал da ондай емес.
Кіріс деректер
Бірінші қатарда екі бүтін сан $n,q$ ($1\le n,q\le100\,000$) — $S$ жолының ұзындығы және өзгерістер саны берілген.
Екінші қатарда ұзындығы $n$ болатын $S$ екілік жолы берілген.
Келесі $q$ қатардың $i$-ші қатарында $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$ жолының әрбір өзгерісі үшін жеке қатарға $10^9+7$ модулі бойынша екі бүтін санды — $X(S)$ және $Y(S)$ мәндерін шығарыңыз.
Мысалдар
Кіріс деректер 1
4 3 0110 0 2 3 1 3 4 F 2 3
Шығыс деректер 1
1 1 2 1 3 4
Ескертпе
Мысалда $S$ жолы 0110-ге тең және $S$ жолына $q=3$ өзгеріс енгізіледі.
Төмендегі кестеде $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$, өйткені $S$ жолының ішкі тізбегі болмайтын ұзындығы $1$-ге тең тек бір ғана жол бар, ол —1жолы.$S=$
0011үшін10жолы ең қысқа болып табылады және ол $S$ жолының ішкі тізбегі болмайтын ұзындығы $2$-ге тең жалғыз жол.$S=$
0101үшін $S$ жолының ішкі тізбегі болмайтын ең қысқа ұзындықтағы жолдар тізімі:{000, 100, 110, 111}.Бастапқы $S=$
0110жолы үшін $S$ жолының ішкі тізбегі болмайтын ең қысқа ұзындықтағы жолдар тізімі:{000, 001, 100, 101, 111}. Сондықтан $X(S)=3$ және $Y(S)=5$, бірақ бұл екі санды шығарудың қажеті жоқ.