D. Сайн дэд тэмдэгт мөрийг тоолох

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

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

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

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

Хэрэв дараалсан бүх ижил тэмдэгтийг нэгтгэсэний дараа үр дүн нь палиндром тэмдэгт мөр байвал үүнийг сайн тэмдэгт мөр гэж нэрллээ. Жишээлбэл "$aabba$" бол сайн тэмдэгт мөр, учир нь нэгтгэх алхам хийсний дараа "$aba$" болно.

Өгөгдсөн тэмдэгт мөрнөөс та хоёр утга олох ёстой. Үүнд:

  1. Тэгш урттай сайн дэд тэмдэгт мөрийн тоо;
  2. Сондгой урттай сайн дэд тэмдэгт мөрийн тоо.

Оролт

Оролтын эхний мөрөнд $n$ ($1 ≤ n ≤ 10^{5}$) урттай нэг тэмдэгт мөр агуулагдана. Тэмдэгт бүр нь '$a$' эсвэл '$b$' байна.

Гаралт

Зайгаар тусгаарлагдсан хоёр бүхэл тоо хэвлэнэ. Эдгээр нь тэгш урттай сайн дэд тэмдэгт мөрийн тоо болон сондгой урттай сайн дэд тэмдэгт мөрийн тоо юм.

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

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

Оролт
bb
Гаралт
1 2
Оролт
baab
Гаралт
2 4
Оролт
babb
Гаралт
2 5
Оролт
babaa
Гаралт
2 7

Тэмдэглэл

1 дүгээр жишээнд, ("$b$", "$b$" ба "$bb$") гэсэн гурван сайн дэд тэмдэгт мөр байна. Тэгш урттай нэг байгаа ба сондгой урттай хоёр ширхэг байна.

2 дугаар жишээнд, ("$b$", "$a$", "$a$", "$b$", "$aa$", "$baab$") гэсэн 6 ширхэг сайн дэд тэмдэгт мөр байна. Тэгш уртай хоёр байгаа ба сондгой урттай дөрвөн ширхэг байна.

3 дугаар жишээнд, ("$b$", "$a$", "$b$", "b$", "bb$", "bab$", "babb$") гэсэн долоон сайн дэд тэмдэгт мөр байна. Тэгш урттай 2 байгаа ба сондгой урттай таван ширхэг байна.

Тодорхойлолт

Тэмдэгт мөр $s = s_{1}s_{2}... s_{n}$-ийн дэд тэмдэгт мөр нь $s[l, r]$ $(1 ≤ l ≤ r ≤ n)$ бол тэмдэг мөр $s_{l}s_{l + 1}... s_{r}$ байна.

Хэрвээ тэмдэгт мөр $s_{n}s_{n - 1}... s_{1}$ нь тэмдэгт мөр $s = s_{1}s_{2}... s_{n}$-тэй ижилхэн бол энэ нь палиндром тэмдэгт мөр юм.

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