A. Гэрийн даалгавар

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

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

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

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

Сергей $N$-иш хэлний хичээлд сууж байв. Хичээл бүр дээр түүнд гэрийн даалгавар өгдөг байжээ. Энэ удаад түүний гэрийн даалгавар нь нэгэн өгүүлбэрийг $N$-иш хэл уруу орчуулах байв. $N$-иш хэлний өгүүлбэр нь Латин жижиг үсгүүдээс тогтох тэмдэгт мөр байх бөгөөд хоосон зай болон таслал цэг агуулаагүй байх ажээ.

Сергей хичээл эхлэхээс 30 минутын өмнө даалгавраа хийх ёстой гэдгийг санасан бөгөөд ямар нэгэн зүйл сараачиж орхижээ. Гэвч дараа нь тэрээр сүүлийн хичээл дээр үзсэн $N$-иш хэлний дүрмээ санав. $N$-иш хэлний үсэглэх дүрэмд "хориотой" хос үсгүүд байдаг ажээ: ийм байх үсгүүд нь өгүүлбэр дотор бие биенийхээ дэргэд зэргэлдээ байдалтайгаар оршин байж болохгүй юм. Түүнчлэн үсгүүдийн дараалал нь хамаагүй. Жишээлбэл хэрэв "$ab$" гэсэн хос үсгүүд нь хориотой байвал "$ab$" болон "$ba$" гэсэн дэд тэмдэгт мөрүүд нь мөн хориотой байна. Мөн хос болгон нь ялгаатай үсгүүдээс тогтох ба үсэг болгон нь нэгээс ихгүй тооны хориотой хос дотор орсон байна.

Одоо Сергей өөрийн бичсэн өгүүлбэрээ дотор нь ямар ч "хориотой" хос үсгүүд ороогүй байхаар засахыг хүсжээ. Тэгсэн хэдий ч түүний хичээл орох цаг дөхөж байгаа учраас тэрээр өгүүлбэр дотроос зарим үсгийг нь дарахаар шийджээ. Тэгвэл түүний дарах ёстой үсгийн хамгийн бага тоог олно уу? Ямар нэгэн үсгийг дарах үед уг үсэг нь "устгагдсан" гэж үзэх бөгөөд ингэснээр уг үсгийн зүүн болон баруун талд байгаа (хэрэв оршин байвал) үсгүүд нь хоорондоо нийлж шинэ өгүүлбэрийг үүсгэх юм. Жишээлбэл хэрэв бид "$aba$" гэсэн тэмдэгт мөрөөс эхний үсгийг дарж хаявал бид "$ba$" гэсэн тэмдэгт мөртэй үлдэх ба хэрэв бид 2-дахь үсгийг дарж хаявал бид "$aa$" гэсэн тэмдэгт мөртэй үлдэх ажээ.

Оролт

Эхний мөрөнд Латин жижиг үсгүүдээс тогтох хоосон биш тэмдэгт мөр $s$ өгөгдөх ба энэ нь Сергей-ын анх бичсэн $N$-иш хэл дээрх өгүүлбэр байх юм. $s$ тэмдэгт мөрийн урт нь $10^{5}$-аас хэтрэхгүй байна.

Дараагийн мөрөнд бүхэл тоо $k$ ($0 ≤ k ≤ 13$) өгөгдөх ба энэ нь хориотой хос үсгүүдийн тоог илэрхийлнэ.

Дараагийн $k$ мөрөнд хориотой хос үсгүүдийн тайлбар өгөгдөнө. Мөр болгонд хориотой хос үсгүүдийг илэрхийлэх хоорондоо ямар ч зайгүй яг 2 ширхэг ялгаатай Латин жижиг үсгүүд өгөгдөнө. Мөн үсэг болгон нь нэгээс ихгүй тооны хориотой хос дотор орсон байна.

Гаралт

Ямар ч хориотой хос үсгүүд агуулаагүй байх тэмдэгт мөр гарган авахын тулд устгах ёстой үсгийн хамгийн бага тоог илэрхийлэх ганц тоог хэвлэнэ үү. Бүх үсгийг устгах нь үргэлж боломжтой байх тул бодлогын хариулт үргэлж оршин байхыг анхаарна уу.

Орчуулсан: Баатархүү

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

Оролт
ababa
1
ab
Гаралт
2
Оролт
codeforces
2
do
cs
Гаралт
1

Тэмдэглэл

Эхний жишээнд та 2 ширхэг $b$ үсгийг устгах хэрэгтэй байна.

2-дахь жишээнд та 2-р эсвэл 3-р үсгийг устгах хэрэгтэй байна. 2-дахь хориотой хос үсгүүд нь бодлогын хариунд огт нөлөөлөхгүй юм.

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