The bear has a string s = s_1s_2... s_{|}s| (record |s| is the string's length), consisting of lowercase English letters. The bear wants to count the number of such pairs of indices i, j (1 ≤ i ≤ j ≤ |s|), that string x(i, j) = s_{i}s_{i} + 1... s_{j} contains at least one string "bear" as a substring.

String x(i, j) contains string "bear", if there is such index k (i ≤ k ≤ j - 3), that s_{k} = b, s_{k} + 1 = e, s_{k} + 2 = a, s_{k} + 3 = r.

Help the bear cope with the given problem.


-----Input-----

The first line contains a non-empty string s (1 ≤ |s| ≤ 5000). It is guaranteed that the string only consists of lowercase English letters.


-----Output-----

Print a single number — the answer to the problem.


-----Examples-----
Input
bearbtear

Output
6

Input
bearaabearc

Output
20



-----Note-----

In the first sample, the following pairs (i, j) match: (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9).

In the second sample, the following pairs (i, j) match: (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).

Difficulty: EASY
Tags: String algorithms

Implementation

Greedy algorithms

Complete search

Mathematics
Skill types: Complete search

Greedy algorithms

Starter code:

Solutions:
(s, start) = (input(), 0)
(n, k) = (len(s), 0)
while True:
	pos = s.find('bear', start)
	if pos < 0:
		print(k)
		break
	(start, k) = (pos + 1, k + (pos - start + 1) * (n - pos - 3))


a = input()
ans = 0
for i in range(0, len(a) - 3):
	b = a.find('bear', i)
	if b >= 0:
		ans += len(a) - 3 - b
print(ans)


import sys, math, heapq, random, collections, bisect

def main():
	st = input()
	count = 0
	while st.find('bear') != -1:
		idx = st.find('bear')
		count = (idx + 1) * (len(st) - (3 + idx)) + count
		st = st[idx + 1:]
	print(count)
main()


s = input()
a = list(map(len, s.split('bear')))
n = len(a)
for i in range(n):
	if 0 < i < n - 1:
		a[i] += 4
	else:
		a[i] += 1
k = r = 0
for i in range(n - 1):
	k += a[i]
	r += a[i] * (len(s) - k - 2)
print(r)


from bisect import bisect_left as bl
string = input()
n = len(string)
occ = [i for i in range(n - 3) if string[i:i + 4] == 'bear']
ans = sum((n - occ[bl(occ, i)] - 3 for i in range(occ[-1] + 1))) if occ else 0
print(ans)


s = input()
l = len(s)
an = 0
ans = [0] * (l + 1)
prev = -1
for i in range(0, l):
	if 'bear' in s[i:i + 4]:
		ans[i] = 1
		an += (i - prev) * (l - i - 3)
		prev = i
print(an)


s = input()
a = len(s)
d = []
ans = 0
e = []
for i in range(a):
	if s[i:i + 4] == 'bear':
		d.append((i, i + 4))
if d:
	ans += (a - d[-1][1] + 1) * (d[-1][0] + 1)
	for i in range(len(d) - 1):
		ans += (d[i + 1][1] - d[i][1]) * (d[i][1] - 3)
	print(ans)
else:
	print(0)


s = str(input())
i = 0
n = len(s)
ans = 0
count = 0
while i < n:
	if s[i:i + 4] == 'bear':
		if count == 0:
			ans = ans + n - i - 4 + 1
			ans = ans + (i - 0) * (n - (i + 3))
			k = i + 1
		else:
			p = i - k
			ans = ans + p * (n - i - 3)
			ans = ans + n - i - 4 + 1
			k = i + 1
		count += 1
		i = i + 4
	else:
		i += 1
print(ans)


s = input()
ans = 0
sindex = 0
for i in range(s.count('bear')):
	cindex = s.index('bear', sindex)
	ans += (len(s) - cindex - 3) * (cindex - sindex + 1)
	sindex = cindex + 1
print(ans)


s = str(input())
a = 0
l = len(s)
l2 = []
while a <= l - 4:
	if s[a:a + 4] == 'bear':
		l2.append(a)
	a += 1
cnt = 0
temp = 0
n = int(len(l2))
for i in range(n):
	cnt += (l2[i] - temp) * (l - l2[i] - 3)
	cnt += l - l2[i] - 3
	temp = l2[i] + 1
print(cnt)


from sys import stdin
debug = False
try:
	import os
	if os.environ['COMPUTERNAME'] == 'KRUEGER-PC':
		debug = True
except KeyError:
	pass

def debug_print(*foo):
	if debug:
		print(foo)
debug_print('debug active')

def print_array(res, size):
	if size:
		print(len(res))
	print(' '.join(map(str, res)))

def input_int_tuple():
	return tuple([x for x in map(int, stdin.readline().split())])

def input_int_array(size=True):
	if size:
		values = stdin.readline().split()
		assert len(values) == 1
	return [x for x in map(int, stdin.readline().split())]

def input_string():
	return stdin.readline().strip()

def problem():
	import re
	bear = 'bear'
	s = input_string()
	diffs = []
	prev = 0
	cnt = 0
	for m in re.finditer(bear, s):
		cnt += 1
		diffs.append(m.start() - prev)
		prev = m.end()
	if cnt > 0:
		diffs.append(len(s) - prev)
	else:
		return 0
	res = 0
	for (i, v) in enumerate(diffs):
		if i > 0:
			v += 3
		if i < len(diffs) - 1:
			v += 3
		res += (v * v - v) // 2 + v
	cor = (len(diffs) - 1) * 3
	res = res - cor
	n = len(s)
	return (n * n - n) // 2 + n - res
print(problem())


import sys

def mi(s):
	return map(int, s.strip().split())

def lmi(s):
	return list(mi(s))

def mf(f, s):
	return map(f, s)

def lmf(f, s):
	return list(mf(f, s))

def main(s):
	intervals = []
	for i in range(len(s) - 3):
		if s[i:i + 4] == 'bear':
			intervals.append((i, i + 3))
	count = 0
	for (e, inter) in enumerate(intervals):
		(i, j) = inter
		if e == len(intervals) - 1:
			right = len(s) - j
			left = i + 1
			count += left * right
		else:
			(n_i, n_j) = intervals[e + 1]
			left = i + 1
			right = n_j - j
			count += left * right
	return count
for (e, line) in enumerate(sys.stdin.readlines()):
	s = line.strip()
print(main(s))


def f(s):
	n = len(s)
	c = 0
	ll = 0
	for i in range(n - 3):
		if s[i:i + 4] == 'bear':
			l = i - ll + 1
			r = n - i - 3
			c += l * r
			ll = i + 1
	return c
s = input()
print(f(s))


x = input()
k = 0
for i in range(len(x)):
	n = x.find('bear', i)
	if n >= 0:
		k += len(x) - n - 3
print(k)


import sys
input = sys.stdin.readline

def ceil(x):
	if x != int(x):
		x = int(x) + 1
	return x

def factorial(x, m):
	val = 1
	while x > 0:
		val = val * x % m
		x -= 1
	return val

def fact(x):
	val = 1
	while x > 0:
		val *= x
		x -= 1
	return val

def swaparr(arr, a, b):
	temp = arr[a]
	arr[a] = arr[b]
	arr[b] = temp

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def nCr(n, k):
	if k > n:
		return 0
	if k > n - k:
		k = n - k
	res = 1
	for i in range(k):
		res = res * (n - i)
		res = res / (i + 1)
	return int(res)

def upper_bound(a, x, lo=0, hi=None):
	if hi == None:
		hi = len(a)
	while lo < hi:
		mid = (lo + hi) // 2
		if a[mid] < x:
			lo = mid + 1
		else:
			hi = mid
	return lo

def primefs(n):
	primes = {}
	while n % 2 == 0 and n > 0:
		primes[2] = primes.get(2, 0) + 1
		n = n // 2
	for i in range(3, int(n ** 0.5) + 2, 2):
		while n % i == 0 and n > 0:
			primes[i] = primes.get(i, 0) + 1
			n = n // i
	if n > 2:
		primes[n] = primes.get(n, 0) + 1
	return primes

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def swap(a, b):
	temp = a
	a = b
	b = temp
	return (a, b)

def find(x, link):
	p = x
	while p != link[p]:
		p = link[p]
	while x != p:
		nex = link[x]
		link[x] = p
		x = nex
	return p

def union(x, y, link, size):
	x = find(x, link)
	y = find(y, link)
	if size[x] < size[y]:
		(x, y) = swap(x, y)
	if x != y:
		size[x] += size[y]
		link[y] = x

def sieve(n):
	prime = [True for i in range(n + 1)]
	(prime[0], prime[1]) = (False, False)
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime
MAXN = int(100000.0 + 5)

def spf_sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, ceil(MAXN ** 0.5), 2):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i
spf = [0 for i in range(MAXN)]

def factoriazation(x):
	res = []
	for i in range(2, int(x ** 0.5) + 1):
		while x % i == 0:
			res.append(i)
			x //= i
	if x != 1:
		res.append(x)
	return res

def int_array():
	return list(map(int, input().strip().split()))

def float_array():
	return list(map(float, input().strip().split()))

def str_array():
	return input().strip().split()
MOD = int(1000000000.0) + 7
CMOD = 998244353
INF = float('inf')
NINF = -float('inf')
from itertools import permutations
import math
from bisect import bisect_left

def solve():
	s = input()
	if s[-1] == '\n':
		s = s[:-1]
	ans = 0
	for i in range(len(s)):
		c = s.find('bear', i)
		if c >= 0:
			ans += len(s) - c - 3
	print(ans)
for _ in range(1):
	solve()


s = input()
ans = 0
x = 0
for i in range(len(s) - 3):
	if s[i] == 'b' and s[i + 1] == 'e' and (s[i + 2] == 'a') and (s[i + 3] == 'r'):
		ans += (i + 1) * (len(s) - i - 3) - (len(s) - i - 3) * x
		x = i + 1
print(ans)


s = input()
start = 0
count = 0
l = len(s)
pre = 0
while True:
	try:
		start = s.index('bear', start) + 1
		before = start - pre
		count += before * (l - start - 2)
		pre = start
	except:
		break
print(count)


def main():
	s = input()
	n = len(s)
	pos = [-1]
	p = 0
	while True:
		p = s.find('bear', p)
		if p == -1:
			break
		pos.append(p)
		p += 4
	ret = 0
	m = len(pos)
	for i in range(1, m):
		ret += (pos[i] - pos[i - 1]) * (n - pos[i] - 3)
	print(ret)
main()


s = input()
ans = 0
for i in range(len(s)):
	part = s[i:]
	if 'bear' in part:
		ans += len(part) - (part.index('bear') + 3)
print(ans)


(s, ans) = (input(), 0)
for i in range(len(s)):
	f = s.find('bear', i)
	if f != -1:
		ans += len(s) - f - 3
print(ans)


s = input()
n = len(s)
(i, j, count) = (0, s.find('bear'), 0)
while j >= 0:
	count += (j - i + 1) * (n - j - 3)
	i = j + 1
	j = s.find('bear', j + 1)
print(count)


def get_bear(s):
	(stop, ocur, index) = (len(s), [], 0)
	while index < stop:
		if s[index:index + 4] == 'bear':
			ocur.append((index, index + 3))
			index += 4
		else:
			index += 1
	return ocur
(s, count) = (input(), 0)
(ch, siz) = (get_bear(s), len(s))
if ch:
	cut = len(ch)
	count += ch[0][0] * (siz - ch[0][1])
	for y in range(1, cut):
		count += siz - ch[y - 1][1]
		count += 3 * (siz - ch[y][1])
		count += (ch[y][0] - ch[y - 1][1] - 1) * (siz - ch[y][1])
	count += siz - ch[-1][1]
	print(count)
else:
	print(0)


s = input()
ans = 0
w = 'bear'
cnt = s.count(w)
for i in range(cnt):
	ans += (s.index(w) + 1) * (len(s) - (s.index(w) + 3))
	s = s[s.index(w) + 1:]
print(ans)


s = input()
answer = 0
last = s.find('bear') + 1
answer += last * (len(s) - last - 2)
s = s[:last - 1] + '####' + s[last + 3:]
last += 1
while 'bear' in s:
	i = s.find('bear') + 1
	answer += (i - last + 1) * (len(s) - i - 2)
	s = s[:i - 1] + '####' + s[i + 3:]
	last = i + 1
print(answer)


s = input()
n = len(s)
prev = 0
ans = 0
for i in range(n - 3):
	if s[i:i + 4] == 'bear':
		bwc = i + 1 - prev
		prev = i + 1
		endchar = n - i - 3
		ans += bwc * endchar
		i += 3
print(ans)


s = input()
res = 0
for i in range(len(s)):
	idx = s.find('bear', i)
	if idx >= 0:
		res += len(s) - idx - 3
print(res)


def get_max_s(s):
	n = len(s)
	i = 0
	l = 0
	count = 0
	while i < n:
		if s[i:i + 4] == 'bear':
			count += (n - (i + 4) + 1) * (i - l + 1)
			l = i + 1
			i += 4
			continue
		i += 1
	return count
s = input().strip()
max_s = get_max_s(s)
print(max_s)
import unittest

class TestFoo(unittest.TestCase):

	def test_world(self):
		got = get_max_s('bearbtear')
		self.assertEqual(got, 6)
		got = get_max_s('bearaabearc')
		self.assertEqual(got, 20)


word = input()
points = 0
y = 0
for i in range(len(word)):
	part = word[i:]
	if 'bear' in part:
		points += len(part) - (part.index('bear') + 3)
print(points)


s = input()
if len(s) < 4:
	print(0)
a = 0
if len(s) >= 4:
	for i in range(len(s)):
		d = s.find('bear', i)
		if d >= 0:
			a += len(s) - d - 3
	print(a)


s = input().rstrip()
x = list(s)
if len(x) < 4:
	print(0)
else:
	l = []
	q = []
	for i in range(0, len(x) - 4 + 1):
		V = x[i:i + 4]
		if ''.join(V) == 'bear':
			l.append(i + 1)
			q.append(i + 4)
	total = 0
	for i in range(0, len(l)):
		if i == 0:
			A = l[i] - 0
			B = q[i]
			total += A * (len(x) - B + 1)
		else:
			A = l[i]
			B = q[i]
			C = l[i - 1]
			D = A - C
			E = len(x) - B + 1
			total += E * D
	print(total)


from sys import stdin, stdout, setrecursionlimit
from gc import disable
gets = input
puts = print
input = stdin.readline
print = stdout.write
p = 31

def search(s: str, t: str) -> list:
	ans = []
	lt = len(t)
	ls = len(s)
	p_pow = [0] * (ls if ls > lt else lt)
	p_pow[0] = 1
	for i in range(1, len(p_pow)):
		p_pow[i] = p_pow[i - 1] * p
	h = [0] * lt
	for i in range(lt):
		h[i] = (ord(t[i]) - 96) * p_pow[i]
		if i:
			h[i] += h[i - 1]
	h_s = 0
	for i in range(ls):
		h_s += (ord(s[i]) - 96) * p_pow[i]
	for i in range(lt + 1 - ls):
		cur_h = h[i + ls - 1]
		if i:
			cur_h -= h[i - 1]
		if cur_h == h_s * p_pow[i]:
			ans.append(i)
	return ans

def main() -> int:
	disable()
	t = gets()
	s = 'bear'
	n = len(t)
	count = -1
	ans = 0
	for i in range(n):
		if i >= 3 and t[i - 3] + t[i - 2] + t[i - 1] + t[i] == s:
			count = i - 3
		ans += count + 1
	print('%i' % ans)
	return 0
main()


s = input().strip()
p = 'bear'
l = len(s)
start = 0
total = 0
while True:
	i = s.find(p, start)
	if i == -1:
		break
	prev = i - start + 1
	multiplier = l - (i + 3)
	total += prev * multiplier
	start = i + 1
print(total)


import sys
import math
from collections import defaultdict
import itertools
MAXNUM = math.inf
MINNUM = -1 * math.inf

def getInt():
	return int(sys.stdin.readline().rstrip())

def getInts():
	return map(int, sys.stdin.readline().rstrip().split(' '))

def getString():
	return sys.stdin.readline().rstrip()

def printOutput(ans):
	sys.stdout.write()
	pass

def saysBear(s, index):
	return s[index - 3:index + 1] == 'bear'

def solve(s):
	count = [0 for _ in range(len(s))]
	strings = 0
	for i in range(3, len(s)):
		if saysBear(s, i):
			strings = i - 2
		count[i] += strings
	return sum(count)

def readinput():
	s = getString()
	print(solve(s))
readinput()


s = input()
(ans, last) = (0, 2)
for i in range(3, len(s)):
	if s[i - 3:i + 1] == 'bear':
		last = i
	ans += last - 2
print(ans)


from sys import stdin

def get_ints():
	return list(map(int, stdin.readline().strip().split()))
s = input()
n = len(s)
ans = 0
for i in range(n):
	f = s[i:].find('bear')
	if f != -1:
		ans += 1 + len(s[i:]) - f - 4
print(ans)


p = input()
(n, t) = (len(p), [len(i) + 6 for i in p.split('bear')])
t[0] -= 3
t[-1] -= 3
print(3 * (len(t) - 1) + (n * (n + 1) - sum((i * (i + 1) for i in t))) // 2)


s = input()
n = len(s)
cnt = 0
ind = 0
for i in range(n):
	if s[i:min(n, i + 4)] == 'bear':
		cnt += (i + 1 - ind) * (n - i - 3)
		ind = i + 1
print(cnt)


s = input()
if len(s) <= 3:
	print(0)
else:
	n = len(s)
	ans = 0
	A = 0
	for i in range(3, n):
		if s[i - 3] + s[i - 2] + s[i - 1] + s[i] == 'bear':
			ans += (i - 3 - A + 1) * (n - i)
			A = i - 2
	print(ans)


s = input()
ans = 0
li = []
for i in range(len(s)):
	if s[i:i + 4] == 'bear':
		li.append(i)
if len(li) == 0:
	print(0)
else:
	k = 0
	start = li[k]
	b = 0
	for i in range(len(s)):
		while i > start:
			try:
				k += 1
				start = li[k]
			except:
				b = 1
				break
		if b:
			break
		ans += len(s) - start - 3
	print(ans)


s = input()
m = 0
n = len(s)
for i in range(n):
	t = s.find('bear', i)
	if t >= 0:
		m += n - t - 3
print(m)


s = input()
starts = []
ind = 0
while ind + 3 < len(s):
	word = s[ind:ind + 4]
	if word == 'bear':
		starts.append(ind)
	ind += 1
if len(starts) == 0:
	print(0)
	exit(0)
start = 0
cnt = 0
while start <= starts[-1]:
	end = None
	for el in starts:
		if el + 3 >= start and el >= start:
			end = el + 3
			break
	cnt += len(s) - end
	start += 1
print(cnt)


import bisect
import collections
import copy
import functools
import heapq
import itertools
import math
import random
import re
import string
import sys
import time
sys.setrecursionlimit(99999)
s = input()
ns = len(s)
p = []
for i in range(3, ns):
	if s[i - 3:i + 1] == 'bear':
		p.append(i - 3)
ans = 0
for i in range(ns):
	j = bisect.bisect_left(p, i)
	if j == len(p):
		break
	else:
		ans += ns - p[j] - 3
print(ans)


s = input()
a = 0
for i in range(len(s)):
	t = s.find('bear', i)
	if t >= 0:
		a += len(s) - t - 3
	else:
		break
print(a)


import math
import random

def main(arr):
	ans = 0
	start = []
	for i in range(len(arr) - 3):
		s = arr[i:i + 4]
		if s == 'bear':
			start.append(i)
	for i in range(len(start)):
		left = -1 if i == 0 else start[i - 1]
		right = len(arr)
		ans += (start[i] - left) * (right - (start[i] + 3))
	return ans
s = input()
print(main(s))


def solve(s):
	index = 0
	ans = 0
	previousB = -1
	bearPresent = []
	while index < len(s):
		if s[index] == 'b' and index + 3 < len(s):
			if s[index + 1] == 'e' and s[index + 2] == 'a' and (s[index + 3] == 'r'):
				before = index - 0 - (previousB + 1) + 1
				after = len(s) - (index + 3)
				ans += before * after
				previousB = index
				index += 4
				continue
		index += 1
	return ans
print(solve(list(input())))


s = input()
k = 0
for i in range(len(s)):
	c = s.find('bear', i)
	if c >= 0:
		k += len(s) - c - 3
print(k)


from collections import namedtuple
import re
s = input()
Index = namedtuple('Index', ['start_idx', 'end_idx'])
substring_idx = []
for m in re.finditer('bear', s):
	substring_idx.append(Index(m.start(), m.end()))
count = 0
prev = -1
for idx in substring_idx:
	before_char = idx.start_idx - (prev + 1) + 1
	after_char = len(s) - idx.end_idx + 1
	count += before_char * after_char
	prev = idx.start_idx
print(count)


s = input()
n = len(s)
res = last = 0
for i in range(n):
	if s[i:i + 4] == 'bear':
		res += (i - last + 1) * (n - i - 3)
		last = i + 1
print(res)


x = list(input())
n = len(x)
c = 0
t = -1
for i in range(n - 3):
	if ''.join(x[i:i + 4]) == 'bear':
		c += (i - t) * (n - i - 3)
		t = i
print(c)


s = input()
ans = 0
n = len(s)
flag = 0
pre = 0
for i in range(n - 3):
	if s[i] == 'b':
		if s[i + 1] == 'e' and s[i + 2] == 'a' and (s[i + 3] == 'r'):
			if flag == 0:
				ans += (i + 1) * (n - i - 3)
				pre = i
				flag = 1
			else:
				ans += (n - i - 3) * (i - pre)
				pre = i
print(ans)


s = input()
t = len(s)
i = 0
c = 0
s1 = ''
r = 0
ans = 0
while i <= t - 4:
	s1 = s[i] + s[i + 1] + s[i + 2] + s[i + 3]
	if s1 == 'bear':
		a = (i - r + 1) * (t - i - 3)
		ans = ans + a
		r = i + 1
	i = i + 1
print(ans)


s = input()
k = 0
l = 0
sstr = -2
count = 0
while sstr != -1:
	sstr = s.find('bear')
	if sstr == -1:
		break
	elif sstr == 0 or sstr == len(s) - 1:
		k += len(s) - 3
	else:
		z = (sstr + 1) * (len(s) - sstr - 3)
		k += z
	s = s[sstr + 1:len(s)]
print(k)


import sys
import math
import collections
import bisect

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()
string = list(get_string())
count = 0
v = -1
for i in range(3, len(string)):
	if string[i] == 'r' and string[i - 1] == 'a' and (string[i - 2] == 'e') and (string[i - 3] == 'b'):
		v = i - 3
	count += v + 1
print(count)


def bear(s):
	b = 0
	for i in range(len(s)):
		c = s.find('bear', i)
		if c >= 0:
			b += len(s) - c - 3
	return b
s = input()
print(bear(s))


s = input()
ind = -1
cnt = 0
for i in range(3, len(s)):
	if s[i - 3:i + 1] == 'bear':
		ind = i - 3
	cnt += ind + 1
print(cnt)


count = 0
s = input()
index = s.find('bear')
rindex = s.rfind('bear')
if index == -1:
	print(0)
else:
	for i in range(rindex + 1):
		pointer = len(s)
		if s[i:pointer].count('bear') > 1:
			count = count + len(s) - (s.find('bear', i) + 4 - 1)
		else:
			count = count + len(s) - (rindex + 4 - 1)
	print(count)


s = input()
n = len(s)
ans = 0
idx = s.find('bear', 0)
pidx = -1
while idx != -1:
	ans += (idx - pidx) * (n - idx - 3)
	pidx = idx
	idx = s.find('bear', idx + 4)
print(ans)


s = input()
res = 0
while 'bear' in s:
	pos_init = s.find('bear')
	pos = pos_init + 3
	res += len(s) - pos
	s = s[1:]
print(res)


s = input()
ans = 0
while s.find('bear') != -1:
	index = s.find('bear')
	ans += (index + 1) * (len(s) - index - 4 + 1)
	s = s[index + 1:]
print(ans)


string = input()
qtd = 0
for (i, letra) in enumerate(string):
	new_string = string[i:]
	if 'bear' in new_string:
		index = new_string.index('bear')
		qtd += len(new_string) - (index + 3)
print(qtd)


s = input()
n = len(s)
c = 0
for i in range(n - 3):
	for j in range(i + 3, n):
		if s[j - 3:j + 1] == 'bear':
			c = c + n - j
			break
print(c)


s = input()
prev = -1
cnt = 0
l = len(s)
for i in range(l - 3):
	if s[i] == 'b':
		if s[i + 1] == 'e':
			if s[i + 2] == 'a':
				if s[i + 3] == 'r':
					if prev == -1:
						cnt += (i + 1) * (l - i - 3)
						prev = i
					else:
						cnt += (i - prev) * (l - i - 3)
						prev = i
print(cnt)


def main():
	s = input()
	jagah = []
	for i in range(len(s) - 3):
		if s[i:i + 4] == 'bear':
			jagah.append(i)
	k = -1
	total = 0
	for i in range(len(jagah)):
		total += (jagah[i] - k) * (len(s) - jagah[i] - 3)
		k = jagah[i]
	print(total)
main()


s = input()
ans = 0
for i in range(len(s)):
	t = s.find('bear', i)
	if t >= 0:
		ans += len(s) - t - 3
print(ans)


import sys

def fastio():
	from io import StringIO
	from atexit import register
	global input
	sys.stdin = StringIO(sys.stdin.read())
	input = lambda : sys.stdin.readline().rstrip('\r\n')
	sys.stdout = StringIO()
	register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))
fastio()

def debug(*var, sep=' ', end='\n'):
	print(*var, file=sys.stderr, end=end, sep=sep)
INF = 10 ** 20
MOD = 10 ** 9 + 7
I = lambda : list(map(int, input().split()))
from math import gcd
from math import ceil
from collections import defaultdict as dd, Counter
from bisect import bisect_left as bl, bisect_right as br
s = input()
n = len(s)
p = [0] * (n + 1)
for i in range(1, n + 1):
	p[i] = p[i - 1] + (s[i - 1:i + 3] == 'bear')
k = [0] * (n + 1)
for i in range(4, n + 1):
	k[i] = k[i - 1] + (s[i - 4:i] == 'bear')
ans = 0
for i in range(1, n + 1):
	for j in range(i + 1, n + 1):
		if k[j] - p[i - 1] and j - i + 1 >= 4:
			ans += 1
print(ans)


S = input().strip()
Words = S.split('bear')
N = len(S)
Amount = N * (N + 1) // 2
if len(Words) > 1:
	K = len(Words[0]) + 3
	Amount -= K * (K + 1) // 2
	K = len(Words[-1]) + 3
	Amount -= K * (K + 1) // 2
	for i in range(1, len(Words) - 1):
		K = len(Words[i]) + 6
		Amount -= K * (K + 1) // 2
	Amount += 3 * (len(Words) - 1)
	print(Amount)
else:
	print(0)


s = input()
n = len(s)
(r, tmp) = (0, 0)
for i in range(n - 3):
	if s[i:i + 4] == 'bear':
		r += (i + 1 - tmp) * (n - i - 3)
		tmp = i + 1
print(r)


def solution():
	s = input()
	l = s.split('bear')
	if len(l) == 1:
		return 0
	ans = 0
	sums = []
	_sum = 0
	for i in range(len(l) - 1):
		_sum += len(l[i])
		if i >= 1:
			_sum += 4
		sums.append(_sum)
	for i in range(len(l) - 1):
		if i == 0:
			ans += (sums[i] + 1) * (len(s) - sums[i] - 4 + 1)
		else:
			ans += (sums[i] - sums[i - 1]) * (len(s) - sums[i] - 4 + 1)
	return ans
print(solution())


a = input()
n = len(a)
c = 0
p = 0
for x in range(n - 3):
	if a[x] == 'b' and a[x + 1] == 'e' and (a[x + 2] == 'a') and (a[x + 3] == 'r'):
		c = c + (x + 1 - p) * (n - x - 3)
		p = x + 1
print(c)


s = input()
a = len(s)
p = -1
n = 0
for x in range(a - 3):
	if s[x:x + 4] == 'bear':
		n += (a - x - 3) * (x - p)
		p = x
print(n)


s = str(input())
n = len(s)
d = 0
dprec = -1
tot = 0
while d < n - 3:
	if s[d:d + 4] == 'bear':
		tot += (d - dprec) * (n - 3 - d)
		dprec = d
		d += 4
	else:
		d += 1
print(tot)


s = input()
temp = s
pair_count = 0
while 'bear' in temp:
	if temp.startswith('bear'):
		pair_count += len(temp) + 1 - 4
		index = 0
	else:
		index = temp.index('bear')
		pair_count += (index + 1) * (len(temp) - index - 4 + 1)
	temp = temp[index + 1:]
print(pair_count)


string = input()
n = len(string)
indexPairs = []
for i in range(n - 3):
	if string[i:i + 4] == 'bear':
		indexPairs.append([i, i + 3])
total = 0
last = -1
for i in range(len(indexPairs)):
	total += (indexPairs[i][0] - last) * (n - indexPairs[i][1])
	last = indexPairs[i][0]
print(total)


import os
import sys
from io import BytesIO, IOBase

def main():
	s = input()
	n = len(s)
	ans = 0
	prev = -2
	for i in range(n - 3):
		if s[i:i + 4] == 'bear':
			ans += (i - prev - 1) * (n - i - 3)
			prev = i - 1
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


s = input()
n = len(s)
idx = [-1]
curIdx = s.find('bear', 0)
cnt = 1
while curIdx > -1:
	idx.append(curIdx)
	cnt = cnt + 1
	curIdx = s.find('bear', curIdx + 1)
ret = 0
for i in range(cnt - 1):
	ret = ret + (idx[i + 1] - idx[i]) * (n - idx[i + 1] - 3)
print(ret)


def main():
	s = input()
	(l, i) = ([], s.find('bear'))
	while i >= 0:
		l.append(i)
		i = s.find('bear', i + 4)
	res = []
	for shift in range(min(len(l), 2)):
		res.append(sum(((i + 1) * (len(s) - j - 3) for (i, j) in zip(l, l[shift:]))))
	res.append(0)
	res.append(0)
	print(res[0] - res[1])

def __starting_point():
	main()
__starting_point()


from sys import stdin, stdout

def main():
	s = stdin.readline().strip()
	count = 0
	n = len(s)
	for i in range(n - 3):
		for j in range(i + 3, n):
			if s[j - 3:j + 1] == 'bear':
				count += n - j
				break
	print(count)
main()


from sys import stdin, stdout
from collections import deque
nmbr = lambda : int(stdin.readline())
lst = lambda : list(map(int, stdin.readline().split()))

def fn(x):
	return x * (x + 1) // 2
for _ in range(1):
	s = input()
	n = len(s)
	dp = [0] * (1 + n)
	for i in range(1, 1 + n):
		if i - 2 >= 0 and s[i - 4:i] == 'bear':
			dp[i] = 3
		else:
			dp[i] = 1 + dp[i - 1]
	print(fn(n) - sum(dp))


word = 'bear'
s = input().rstrip()
bears = [(-1, 0)]
for i in range(len(s) - 3):
	flag = 1
	for j in range(4):
		if s[i + j] != word[j]:
			flag = 0
	if flag:
		bears.append((i, i + j))
bears.append((len(s), len(s)))
ans = 0
for i in range(1, len(bears) - 1):
	ans += (bears[i][0] - bears[i - 1][0]) * (len(s) - bears[i][1])
print(ans)


from collections import Counter
import string
import math
import sys

def array_int():
	return [int(i) for i in sys.stdin.readline().split()]

def vary(number_of_variables):
	if number_of_variables == 1:
		return int(sys.stdin.readline())
	if number_of_variables >= 2:
		return map(int, sys.stdin.readline().split())

def makedict(var):
	return dict(Counter(var))
mod = 100000007
s = input()
ans = 0
i = 0
while i < len(s) - 3:
	tt = s[i:].find('bear')
	if tt == -1:
		ans += 0
	else:
		ans += len(s[i:]) - (tt + 3)
	i += 1
print(ans)


s = input()
c = s.count('bear')
if c == 0:
	print(0)
	exit()
n = len(s)
a = []
for i in range(0, len(s) - 3):
	t = ''
	t = s[i:i + 4]
	if t == 'bear':
		a.append(i)
		i += 4
pre = ans = 0
for i in a:
	j = i - pre + 1
	k = n - (i + 3)
	ans += j * k
	pre = i + 1
print(ans)


s = input()
l = len(s)
import re
total = 0
prev = -1
for m in re.finditer('bear', s):
	total += (m.start() - prev) * (l - (m.start() + 3))
	prev = m.start()
print(total)


z = list(map(str, input()))
x = ['b', 'e', 'a', 'r']
a = 0
ans = 0
for i in range(len(z) - 3):
	a += 1
	if z[i:i + 4] == x:
		ans += a * (len(z) - (i + 4)) + a
		a = 0
print(ans)


s = input()
n = len(s)
ans = 0
for i in range(n):
	ind = s.find('bear', i)
	if ind >= 0:
		ans += n - 3 - ind
print(ans)


def function(s):
	count = 0
	for i in range(len(s)):
		t = s.find('bear', i)
		if t >= 0:
			count += len(s) - t - 3
	print(count)
s = input()
function(s)


s = input()
n = len(s)
kol = 0
posl_i = 0
tek_i = s.find('bear', 0, n)
while tek_i != -1:
	kol += (tek_i - posl_i + 1) * (n - tek_i - 3)
	posl_i = tek_i + 1
	tek_i = s.find('bear', tek_i + 1, n)
print(kol)


def solve(s):
	arr = []
	n = len(s)
	for i in range(n):
		if i + 3 < n and s[i] == 'b' and (s[i + 1] == 'e') and (s[i + 2] == 'a') and (s[i + 3] == 'r'):
			arr.append(i)
	ans = 0
	l = len(arr)
	for j in range(l):
		after = n - (arr[j] + 4)
		before = 0
		afterBefore = 0
		if j == 0:
			before = arr[j] - 0
			afterBefore = before * after
		if j > 0:
			before = arr[j] - arr[j - 1] - 1
			afterBefore = before * after
		ans += after + before + afterBefore + 1
	print(ans)

def run():
	s = input()
	solve(s)
run()


s = input()
r = 0
ans = 0
n = len(s)
for i in range(n):
	if s[i:4 + i] == 'bear':
		temp2 = i - r
		temp = n - (4 + i)
		ans += temp2 * temp + (temp2 + temp) + 1
		r = i + 1
print(ans)


s = input()
pos = [-1]
x = 'bear'
for i in range(len(s) - 3):
	if s[i:i + 4] == x:
		pos.append(i)
count = 0
n = len(s)
if len(pos) > 1:
	for i in range(1, len(pos)):
		k = n - pos[i] - 3
		count += k * (pos[i] - pos[i - 1])
print(count)


from collections import defaultdict, deque, Counter, OrderedDict

def main():
	ans = 0
	s = input()
	n = len(s)
	for i in range(n):
		ind = s.find('bear', i)
		if ind < 0:
			continue
		j = ind + 3
		ans += n - j
	print(ans)
main()


from sys import stdin, stdout
from os import path
if path.exists('input.txt'):
	stdin = open('input.txt', 'r')
x = stdin.readline()
k = 0
for i in range(len(x)):
	t = x.find('bear', i)
	if t >= 0:
		k += len(x) - t - 4
stdout.write(str(k) + '\n')


from math import ceil
s = input()
n = len(s)
ans = 0
last_idx = -1
for i in range(n - 3):
	if s[i:i + 4] == 'bear':
		if i == 0:
			ans += n - 1 - (i + 3) + 1
			last_idx = i
		else:
			k = i - last_idx - 1
			k1 = n - 1 - (i + 3) + 1
			ans += k * k1
			ans += k1
			last_idx = i
print(ans)


def main():
	s = input()
	l = len(s)
	a = []
	n = 0
	for i in range(l - 3):
		if s[i:i + 4] == 'bear':
			n += 1
			a.append(i)
	if n == 0:
		print(0)
		exit(0)
	ans = (a[-1] + 1) * (l - a[-1] - 3)
	if n > 1:
		for i in range(n - 2, -1, -1):
			ans += (a[i] + 1) * (a[i + 1] - a[i])
	print(ans)
main()


s = input()
count = 0
o = [0]
i = 0
while True:
	bb = s.find('bear', i, len(s))
	if bb is not -1:
		o.append(bb)
	i = bb + 1
	if i >= len(s) - 3 or bb == -1:
		break
for i in range(1, len(o)):
	if i == 1:
		count += o[i] * (len(s) - o[i] - 4) + o[i] + (len(s) - o[i] - 4) + 1
	else:
		count += (o[i] - o[i - 1] - 1) * (len(s) - o[i] - 4) + (o[i] - o[i - 1] - 1) + (len(s) - o[i] - 4) + 1
print(count)


s = input()
n = len(s)
ans = 0
lb = -1
for i in range(n - 3):
	if s[i:i + 4] == 'bear':
		left = i - lb
		right = n - 3 - i
		ans += left * right
		lb = i
print(ans)


s = input()
ind = [i for (i, _) in enumerate(s) if s.startswith('bear', i)]
(L, r, z) = (len(s), 0, 0)
for e in ind:
	r += (e + 1 - z) * (L - (e + 3))
	z = e + 1
print(r)


s = input()
sm = 0
n = len(s)
temp = -1
for i in range(n - 3):
	if s[i] == 'b' and s[i + 1] == 'e' and (s[i + 2] == 'a') and (s[i + 3] == 'r'):
		sm += (i - temp) * (n - 3 - i)
		temp = i
print(sm)


s = input()
sum = 0
for i in range(len(s)):
	n = s.find('bear', i)
	if n == -1:
		break
	sum += len(s) - (n + 4) + 1
print(sum)


s = input().rstrip()
n = len(s)
(ans, l, r) = (0, 0, s.find('bear'))
while r >= 0:
	ans += (r - l + 1) * (n - r - 3)
	(l, r) = (r + 1, s.find('bear', r + 1))
print(ans)


string = input()
result = 0
pos = string.find('bear')
while pos >= 0:
	result += len(string) - (pos + 3)
	string = string[1:]
	pos = string.find('bear')
print(result)


x = input()
count = 0
while 'bear' in x:
	start = x.index('bear')
	count += (start + 1) * (len(x) - start - 4 + 1)
	x = x[start + 1:]
print(count)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def fact(x):
	if x == 0:
		return 1
	else:
		return x * fact(x - 1)

def lower_bound(li, num):
	answer = -1
	start = 0
	end = len(li) - 1
	while start <= end:
		middle = (end + start) // 2
		if li[middle] >= num:
			answer = middle
			end = middle - 1
		else:
			start = middle + 1
	return answer

def upper_bound(li, num):
	answer = -1
	start = 0
	end = len(li) - 1
	while start <= end:
		middle = (end + start) // 2
		if li[middle] <= num:
			answer = middle
			start = middle + 1
		else:
			end = middle - 1
	return answer

def abs(x):
	return x if x >= 0 else -x

def binary_search(li, val, lb, ub):
	ans = 0
	while lb <= ub:
		mid = (lb + ub) // 2
		if li[mid] > val:
			ub = mid - 1
		elif val > li[mid]:
			lb = mid + 1
		else:
			ans = 1
			break
	return ans
for _ in range(1):
	string = input()
	(n, ans) = (len(string), 0)
	for i in range(n - 3):
		for j in range(i + 3, n):
			if string[j - 3:j + 1] == 'bear':
				ans += n - j
				break
	print(ans)


import re
s = input()
bears = [-1] + [m.start() for m in re.finditer('bear', s)]
sol = 0
for i in range(1, len(bears)):
	sol += (bears[i] - bears[i - 1]) * (len(s) - bears[i] - 3)
print(sol)


s = input()
n = len(s)
starts = []
for i in range(n):
	if s[i:i + 4] == 'bear':
		starts.append(i + 1)
x = len(starts)
j = 0
answer = 0
for i in range(n):
	try:
		if i + 1 == starts[j]:
			answer += n - i - 3
			j += 1
		elif j < x:
			answer += n - (starts[j] + 2)
	except IndexError:
		pass
print(answer)


from collections import *
s = input()
(num, ixs, beg) = (s.count('bear'), deque([]), 0)
for i in range(num, 0, -1):
	ixs.append(s.find('bear', beg) + 1)
	beg = ixs[-1] + 3
(beg, ans) = (0, 0)
if ixs == deque([]):
	exit(print(0))
for i in range(1, len(s) - 2):
	while ixs[beg] < i:
		beg += 1
		if beg == num:
			exit(print(ans))
	for j in range(ixs[beg] + 3, len(s) + 1):
		ans += 1
print(ans)


inp = input()
n = len(inp) - 3
res = 0
for i in range(n):
	for j in range(i, n):
		if inp[j] == 'b':
			if inp[j + 1] == 'e':
				if inp[j + 2] == 'a':
					if inp[j + 3] == 'r':
						res += n - j
						break
print(res)


s = input().strip()
n = len(s)
x = []
for i in range(n - 3):
	if s[i:i + 4] == 'bear':
		x.append(i)
i = 0
j = 0
ans = 0
m = len(x)
while i < m:
	ans += max(0, n - x[i] - 3)
	j += 1
	if j > x[i]:
		i += 1
print(ans)


x = input()
sm = 0
for i in range(len(x)):
	t = x.find('bear', i)
	if t >= 0:
		sm += len(x) - t - 3
print(sm)


s = str(input())
n = len(s)
vec = list()
for i in range(n - 3):
	if s[i] == 'b' and s[i + 1] == 'e' and (s[i + 2] == 'a') and (s[i + 3] == 'r'):
		vec.append(i + 1)
size = len(vec)
x = 1
ans = 0
for i in range(size):
	y = n - vec[i] - 2
	if i:
		x = vec[i - 1] + 1
	x = vec[i] - x + 1
	ans += x * y
print(ans)


import logging
import copy
import sys
import re
logging.basicConfig(stream=sys.stderr, level=logging.DEBUG)

def solve(text):
	s = 0
	startIdx = []
	for i in range(len(text) - 3):
		if text[i:i + 4] == 'bear':
			startIdx.append(i)
	for (idx, i) in enumerate(startIdx):
		lastCount = len(text) - (i + 4) + 1
		if idx == 0:
			s += (i + 1) * lastCount
		else:
			s += (i - startIdx[idx - 1]) * (len(text) - (i + 4) + 1)
	return s

def main():
	firstLine = input()
	print(solve(firstLine.strip()))

def log(*message):
	logging.debug(message)
main()


s = input()
if len(s) < 4 or (len(s) == 4 and s[0] != 'b' and (s[-1] != 'r')):
	print(0)
	exit(0)
if 'bear' not in s:
	print(0)
	exit(0)
else:
	n = len(s)
	count = 0
	flag = -1
	for i in range(n - 3):
		if s[i:i + 4] == 'bear':
			count += (i - flag) * (n - 3 - i)
			flag = i
	print(count)


string = input()
i = 0
last = 0
total = 0
while i < len(string) - 3:
	if string[i] == 'b' and string[i + 1] == 'e' and (string[i + 2] == 'a') and (string[i + 3] == 'r'):
		total += (i + 1) * (len(string) - i - 3)
		string = string[i + 1:]
		i = 0
	i += 1
print(total)


import os
import re
import sys
from bisect import bisect, bisect_left, insort, insort_left
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from io import BytesIO, IOBase
from itertools import accumulate, combinations, combinations_with_replacement, groupby, permutations, product
from math import acos, asin, atan, ceil, cos, degrees, factorial, hypot, log2, pi, radians, sin, sqrt, tan
from operator import itemgetter, mul
from string import ascii_lowercase, ascii_uppercase, digits

def inp():
	return int(input())

def inlist():
	return list(map(int, input().split()))

def instr():
	s = input()
	return list(s[:len(s)])

def invr():
	return map(int, input().split())

def found(i, a):
	if a[i:i + 4] == 'bear':
		return True
	return False

def main():
	a = input()
	n = len(a)
	res = 0
	i = 0
	prev = -1
	while i < n - 3:
		if found(i, a):
			x = max(0, n - (i + 3))
			for j in range(prev + 1, i + 1):
				res += x
			prev = i
			i += 3
		i += 1
	print(res)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')
main()