B. Баавгай ба тэмдэгт мөр

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

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

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

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

Баавгайд Англи жижиг үсэгнээс бүтсэн $s = s_{1}s_{2}... s_{|s|}$ ($|s|$ бол тэмдэгт мөрийн урт) тэмдэгт мөр байна. Баавгай $x(i, j) = s_{i}s_{i + 1}... s_{j}$ нь хамгийн багадаа нэг "$bear$" дэд тэмдэгт мөрийг агуулсан байх $i, j$ $(1 ≤ i ≤ j ≤ |s|)$ хосуудын тоог олохыг хүссэн.

Хэрвээ $(i ≤ k ≤ j - 3)$ ба $s_{k} = b$, $s_{k + 1} = e$, $s_{k + 2} = a$, $s_{k + 3} = r$ байх $k$ индекс байдаг бол $x(i, j)$ тэмдэгт мөр нь "$bear$" тэмдэгт мөрийг агуулна.

Байвгайд өгөгдсөн асуудлыг даван туулахад нь тусал.

Оролт

Эхний мөр нь хоосон биш $s$ $(1 ≤ |s| ≤ 5000)$ тэмдэгт мөрийг агуулна. Тэмдэгт мөр нь зөвхөн Англи жижиг үсэгнээс бүрдэнэ.

Гаралт

Асуултын хариулт болох нэг тоо хэвлэнэ.

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

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

Оролт
bearbtear
Гаралт
6
Оролт
bearaabearc
Гаралт
20

Тэмдэглэл

Эхний жишээнд, дараах $(i, j)$ хосууд тохирно: $(1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9)$.

Хоёр дахь жишээнд, дараах $(i, j)$ хосууд тохирно: $(1,  4), (1,  5), (1,  6), (1,  7), (1,  8), (1,  9), (1,  10), (1,  11), (2,  10), (2,  11), (3,  10), (3,  11), (4,  10), (4,  11), (5,  10), (5,  11), (6,  10), (6,  11), (7,  10), (7,  11)$.

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