D. Сайн дэд тэмдэгт мөр

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 512 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Танд Англи жижиг үсэгнүүдээс бүрдсэн $s$ тэмдэгт мөр байна. Англи үсэгнүүдийн зарим үсэг нь сайн, үлдсэн үсэгнүүд нь муу байна.

$s = s_{1}s_{2}...s_{|s|}$ ($|s|$ гэдэг нь $s$ тэмдэгт мөрийн урт) тэмдэгт мөрийн $s[l...r]$ ($1 ≤ l ≤ r ≤ |s|$) дэд тэмдэгт мөр гэдэг нь $ s_{l}s_{l + 1}...s_{r}$ тэмдэгт мөр юм.

$ s_{l}, s_{l + 1}, ..., s_{r}$ үсэгнүүдийн дунд хамгийн ихдээ $k$ ширхэг муу үсэгнүүд байдаг бол $s[l...r]$-г сайн тэмдэгт мөр гэнэ (илүү сайн ойлгохыг хүсвэл жишээний тайлбарыг харна уу).

Таны даалгавар бол өгөгдсөн $s$ тэмдэгт мөрийн ялгаатай сайн дэд тэмдэгт мөрүүдийн тоог олох юм. Хэрвээ агуулга нь ялгаатай бол $s[x...y]$ ба $s[p...q]$ тэмдэгт мөрүүдийг ялгаатай гэнэ. Өөрөөр хэлбэл $s[x...y] ≠ s[p...q]$ байна.

Оролт

Оролтын эхний мөр нь Англи жижиг үсэгнүүдээс бүрдсэн, хоосон биш $s$ тэмдэгт мөрийг агуулна. Энэ тэмдэгт мөрийн урт нь хамгийн ихдээ $1500$ тэмдэгт байна.

Оролтын хоёр дахь мөр нь яг $26$ тэмдэгтийн урттай "0" ба "1"-ийн тэмдэгтүүд агуулсан тэмдэгт мөр байна. Энэ тэмдэгт мөрийн $i$-р тэмдэгт нь "1" бол $i$-р Англи үсгийг сайн, эсрэг тохиолдолд муу гэнэ. Энэ тэмдэгт мөрийн эхний тэмдэгт нь "a" үсэгтэй, хоёр дахь тэмдэгт нь "b" үсэгтэй гэх мэтчилэн харгалзана.

Оролтын гурав дахь мөр нь $k$ ($0 ≤ k ≤ |s|$) бүхэл тоог агуулна. Энэ нь сайн тэмдэгт мөрөнд байж болох муу тэмдэгтүүдийн тоо юм.

Гаралт

Нэг бүхэл тоо хэвлэнэ. Энэ нь $s$ тэмдэгт мөрийн ялгаатай сайн дэд тэмдэгт мөрүүдийн тоо.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
ababab
01000000000000000000000000
1
Гаралт
5
Оролт
acbacbacaa
00000000000000000000000000
2
Гаралт
8

Тэмдэглэл

Эхний жишээнд дараах сайн дэд тэмдэгт мөрүүд байна: "$a$", "$ab$", "$b$", "$ba$", "$bab$".

Хоёр дахь жишээнд дараах сайн дэд тэмдэгт мөрүүд байна: "$a$", "$aa$", "$ac$", "$b$", "$ba$", "$c$", "$ca$", "$cb$".

Сэтгэгдлүүдийг ачааллаж байна...