Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

def solve():
    from sys import stdin
    f_i = stdin
    
    H, W = map(int, f_i.readline().split())
    
    grid = ['W'] * (W + 2)
    for i in range(H):
        grid += ['W'] + list(f_i.readline().rstrip()) + ['W']
    grid += ['W'] * (W + 2)
    
    adj = (1, -1, W + 2, -W - 2)
    cnt = 0
    next_grid = grid[:]
    while True:
        if '.' not in grid:
            print(cnt)
            break
        
        cnt += 1
        
        idx = 0
        while True:
            try:
                idx = grid.index('.', idx)
                for a in adj:
                    adj_pos = idx + a
                    if grid[adj_pos] == '#':
                        next_grid[idx] = '#'
                        break
                idx += 1
            except ValueError:
                break
        
        grid = next_grid[:]

solve()

### FIXED CODE ###

def solve():
    from collections import deque
    from sys import stdin
    f_i = stdin
    
    H, W = map(int, f_i.readline().split())
    
    grid = ['W'] * (W + 2)
    for i in range(H):
        grid += ['W'] + list(f_i.readline().rstrip()) + ['W']
    grid += ['W'] * (W + 2)
    
    q = deque()
    for i, cell in enumerate(grid):
        if cell == '#':
            q.append((i, 0)) # (pos, operation count)
    move = (1, -1, W + 2, -W - 2)
    
    while q:
        pos, count = q.popleft()
        for mv in move:
            next_pos = pos + mv
            if grid[next_pos] == '.':
                grid[next_pos] = '#'
                q.append((next_pos, count + 1))
    
    print(count)
    
solve()
### BUGGY CODE ###

n, k = map(int,input().split())
a = list(map(int,input().split()))


s1 = 1
s2 = 1
for i in range(k):
  s1 = s1 * a[i]
  s2 = s2 * a[i+1]

if s1 < s2:
  print("Yes")
else:
  print("No")


for i in range(1,n-k):
  s1 = s2
  s2 = int(s1 / a[i] * a[k+i])
    
  if s1 < s2:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

n, k = map(int,input().split())
a = list(map(int,input().split()))


for i in range(n-k):
    
  if a[i] < a[k+i]:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

N = int(input())
s = input()

times = len(s)
for i in range(len(s) + 1):
    r, l = s[:i], s[i:]
    if times > max(r.count("W"), l.count("R")):
        times = max(r.count("W"), l.count("R"))
print(times)

### FIXED CODE ###

N = int(input())
s = input()

R, L = 0, s.count("R")
times = max(R, L)
for c in s:
    if c == "W":
        R += 1
    else:
        L -= 1
    if times > max(R, L):
        times = max(R, L)
print(times)
### BUGGY CODE ###

N = int(input())
L = sorted([int(i) for i in input().split()], reverse=True)

def count(ls, n):
    left = 0
    right = len(ls)
    while right - left > 1:
        mid = (left + right) // 2

        if ls[mid] > n: left = mid
        if ls[mid] <= n: right = mid

    return left

ans = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        ans += count(L[j:], L[i]-L[j])

print(ans)

### FIXED CODE ###

from bisect import bisect_left

N = int(input())
L = sorted([int(i) for i in input().split()])

ans = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        ans += bisect_left(L, L[i]+L[j]) - (j + 1)

print(ans)
### BUGGY CODE ###

#coding utf-8
N,M=map(int,input().split())
a =[int(input()) for i in range(M)]
mod =10**9+7
dp = [1]
for i in range(1,N+1):
  if i not in a:
    if i ==1:
      dp.append(dp[-1])
    else:
      dp.append((dp[-1]+dp[-2])%mod)
  else:
    dp.append(0)

print(dp[-1])

### FIXED CODE ###

#coding utf-8
N,M=map(int,input().split())
a =[int(input()) for i in range(M)]
a.append(0)
mod =10**9+7
dp = [1]
j = 0
for i in range(1,N+1):
  if i != a[j]:
    if i ==1:
      dp.append(dp[-1])
    else:
      dp.append((dp[-1]+dp[-2])%mod)
  else:
    dp.append(0)
    j +=1 

print(dp[-1])
### BUGGY CODE ###

n=int(input())
print(1)
s=input()
if s="Vacant":
  exit(0)

l=1
r=n

for i in range(20):

  if r-l<=2:
    for i in range(3):
      print(l+1, flush=True)
      s=input()
      if s="Vacant":
        exit(0)

      
  elif (r-l+1)%4==1:
    print((l+r)//2, flush=True)
    sn=input()
    if sn="Vacant":
      exit(0)
    elif s==sn:
      l=(l+r)//2
    else:
      r=(l+r)//2
    s=sn

  else:
    print((l+r)//2-1, flush=True)
    sn=input()
    if sn="Vacant":
      exit(0)
    elif s==sn:
      l=(l+r)//2-1
    else:
      r=(l+r)//2-1
    s=sn

### FIXED CODE ###

n=int(input())
print(0, flush=True)
sl=input()
if sl=="Vacant":
  exit(0)

l=0
r=n-1

for i in range(30):

  if r-l<=2:
    for j in range(3):
      print(l+j+1, flush=True)
      s=input()
      if s=="Vacant":
        exit(0)

      
  elif ((l+r)//2)%2==0:
    print((l+r)//2, flush=True)
    s=input()
    if s=="Vacant":
      exit(0)
    elif s==sl:
      l=(l+r)//2
      sl=s
    else:
      r=(l+r)//2
      sr=s

  else:
    print((l+r)//2+1, flush=True)
    s=input()
    if s=="Vacant":
      exit(0)
    elif s==sl:
      l=(l+r)//2
      sl=s
    else:
      r=(l+r)//2
      sr=s
### BUGGY CODE ###


# 分割した配列をソート
def merge(input: list, m: int)-> list:
    i, j = 0, m
    input_len = len(input)
    tmp_nums = []

    for k in range(0, input_len):
        if j > input_len - 1:
            tmp_nums.insert(k, input[i])
            i += 1
        elif i > m - 1:
            tmp_nums.insert(k, input[j])
            j += 1
        elif input[i] < input[j]:
            tmp_nums.insert(k, input[i])
            i += 1
        else:
            tmp_nums.insert(k, input[j])
            j += 1

    return tmp_nums

# 再帰でマージソート
def merge_sort(input: list)-> list:
    input_len = len(input)
    compare_num = input_len

    if input_len > 1:
        m = int(input_len / 2)
        out = merge_sort(input[:m])
        input[:m] = out[0]
        compare_num += out[1]

        out = merge_sort(input[m:])
        input[m:] = out[0]
        compare_num += out[1]

        input = merge(input, m)

    return input, compare_num

n = int(input())
input_list = list(map(int, input().split(' ')))

input_list = merge_sort(input_list)

print(*input_list[0])
print(input_list[1] - n)


### FIXED CODE ###

count = 0

def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L, R = A[left: left + n1], A[mid: mid + n2]

    L.append(2000000000)
    R.append(2000000000)

    i, j = 0, 0
    for k in range(left, right):
        global count
        count += 1
        #print("k", k, "l", left, "m", mid, "r", right, "L", L, "R", R)
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

def mergeSort(A, left, right):
    #print("l", left, "r", right)
    if left + 1 < right:
        mid = (left + right) // 2
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)

n = int(input())
input_list = list(map(int, input().split(' ')))

mergeSort(input_list, 0, n)

print(*input_list)
print(count)
### BUGGY CODE ###

# n ^ m (繰り返し二乗法) (mod p)
def power_mod(n, m, p):
    if m == 0:
        return 1
    if m % 2 == 0:
        d = power_mod(n, m // 2, p)
        return (d * d) % p
    else:
        return (n * power_mod(n, m - 1, p)) % p


# a ^ (p-2) ≡ a^(-1) (mod p)
def gyakugenn(a, p):
    return power_mod(a, p - 2, p)


# nCk (mod p)
# n!/(n-k)!k!
def mod_comb(n, k, p):
    rep = 1
    for i in range(1, n + 1):
        rep = rep * i % p
    for i in range(1, k + 1):
        rep = rep * gyakugenn(i, p) % p
    for i in range(1, n - k + 1):
        rep = rep * gyakugenn(i, p) % p
    return rep


X, Y = map(int, input().split())
x = (2 * Y - X) / 3
y = (2 * X - Y) / 3

if (2 * Y - X) % 3 != 0 or (2 * X - Y) % 3 != 0:
    print(0)
    exit()
else:
    x = int(x)
    y = int(y)

if x < 0 or y < 0:
    print(0)
    exit()

if x < y:
    x, y = y, x

p = 10 ** 9 + 7
print(mod_comb(x + y, y, p))


### FIXED CODE ###


def extgcd(a, b):
    r = [1, 0, a]
    w = [0, 1, b]
    while w[2] != 1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0], r[1]-q*w[1], r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0], w[1]]


def mod_inv(a, m):
    x = extgcd(a, m)[0]
    return (m+x % m) % m


def mod_e(n, p):
    res = 0
    while n >= p:
        res += n//p
        n = n//p
    return res


def mod_fact(n, p):
    if n == 0:
        return 1

    res = mod_fact(n//p, p)

    if n//p % 2 != 0:
        return res*(p-fact[n % p]) % p
    return res*fact[n % p] % p


# nCk mod p
def mod_comb(n, k, p):
    if n < 0 or k < 0 or n < k:
        return 0
    e1 = mod_e(n, p)
    e2 = mod_e(k, p)
    e3 = mod_e(n-k, p)
    #pで割り切れる場合
    if e1 > e2 + e3:
        return 0

    #pで割り切れない場合
    a1 = mod_fact(n, p)
    a2 = mod_fact(k, p)
    a3 = mod_fact(n-k, p)
    return a1 * mod_inv(a2*a3 % p, p) % p

X, Y = map(int, input().split())
x = (2 * Y - X) / 3
y = (2 * X - Y) / 3

# print(x, y)

if (2 * Y - X) % 3 != 0 or (2 * X - Y) % 3 != 0:
    print(0)
    exit()
else:
    x = int(x)
    y = int(y)

if x < 0 or y < 0:
    print(0)
    exit()
# print(x,y)
if x < y:
    x, y = y, x

#pは素数とする
p = 10**9+7

#fact[i] : i! modp (0<= i <p) O(p)
#上だとO(p)なのでnまでにして O(n)にする
fact = [1]
k = 1
for i in range(1, 10**6+100):
    k = k*i % p
    fact.append(k)

#10000C4000 mod 10**9+7
print(mod_comb(x + y, y, p))
### BUGGY CODE ###

from collections import Counter
N,K = map(int,input().split())
A = list(map(int,input().split()))
count = Counter(A)
rew = 0
if K >= len(count):
    print(0)
else:
    values = sorted(list(count.values()))
    while len(values) != K:
        rew += values.pop(0)
    print(rew)

### FIXED CODE ###

from collections import Counter
N,K = map(int,input().split())
A = list(map(int,input().split()))
count = Counter(A)
if K >= len(count):
    print(0)
else:
    values = sorted(list(count.values()),reverse = True)
    del values[:K]
    print(sum(values))
### BUGGY CODE ###

n = int(input())
a_lst = list(map(int, input().split()))
for i in range(n):
    a_lst[i] %= (10 ** 9 + 7)

lst = []
for i in range(n):
        lst.append((sum(a_lst) - sum(a_lst[: i + 1])) % (10 ** 9 + 7))

ans = 0
for i in range(n - 1):
    ans += (a_lst[i] * lst[i]) % (10 ** 9 + 7)
ans %= 10 ** 9 + 7
print(ans)

### FIXED CODE ###

n = int(input())
a_lst = list(map(int, input().split()))

a_lst.reverse()
tmp = a_lst[0]
lst = []
for i in range(1, n):
    lst.append(tmp)
    tmp += a_lst[i]
    tmp %= (10 ** 9 + 7)
lst.reverse()
a_lst.reverse()

ans = 0
for i in range(n - 1):
    ans += (a_lst[i] * lst[i]) % (10 ** 9 + 7)
ans %= (10 ** 9 + 7)
print(ans)
### BUGGY CODE ###

import numpy as np


def main():
	#N, D = [int(x) for x in input().split()]
	N = int(input())
	
	lst = []
	for i in range(N):
		lst.append(int(input()))

	a = np.array(lst)
	
	for i in range(N):
		mask = [True] * N
		mask[i] = False
		mask = np.array(mask)
		_a = a[mask]
		print(np.max(_a))

if __name__ == "__main__":
	main()


### FIXED CODE ###

import numpy as np


def main():
	#N, D = [int(x) for x in input().split()]
	N = int(input())
	
	max_num = 0
	sub_max = 0
	index = 0
	for i in range(N):
		num = int(input())
		if num > max_num:
			index = i
			sub_max = max_num
			max_num = num
		elif num > sub_max:
			sub_max = num

	for i in range(N):
		if i == index:
			print(sub_max)
		else:
			print(max_num)

if __name__ == "__main__":
	main()
### BUGGY CODE ###

s = input()[::-1]
keys = ["dream", "dreamer", "erase", "eraser"]
keys_ = [i[::-1] for i in keys]
i = 0
t = ''

while(i < len(s)):
  for key in keys_:
    if s[i:].startswith(key):
      t += key
      i += len(key)
    if t == s:
      print('YES')
      exit()
    else:
      continue
else:
  print('NO')

### FIXED CODE ###

s = input()[::-1]
keys = ["dream", "dreamer", "erase", "eraser"]
keys_ = [i[::-1] for i in keys]
i = 0
t = ''

for _ in range(len(s)):
  for key in keys_:
    if s[i:].startswith(key):
      t += key
      i += len(key)
    if t == s:
      print('YES')
      exit()
else:
  print('NO')
### BUGGY CODE ###

### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

def resolve():
    readline=sys.stdin.readline
    mod=10**9+7
    n=int(readline())
    arr=list(map(int, readline().rstrip().split()))
    cnt=[0]*60
    for i in range(n):
        b = bin(arr[i])
        j = -1
        while b[j]!="b":
            if b[j]=="1":
                k=j*-1 -1
                cnt[k]+=1
            j-=1

    ans=[0]*60
    answer = 0
    for i in range(60):
        ans[i]=(cnt[i] * (n-cnt[i]))%mod
    x=1
    for i in range(60):
        answer += ans[i]*x
        answer %= mod
        x*=2
        x%=mod
    print(answer)
    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

### FIXED CODE ###

### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

def resolve():
    readline=sys.stdin.readline
    mod=10**9+7
    n=int(readline())
    arr=list(map(int, readline().rstrip().split()))
    binArr = [[0 for i in range(60)] for j in range(n)]
    cnt=[0]*60
    for i in range(n):
        b = bin(arr[i])[2:]
        lenb = len(b)
        for j in range(lenb):
            binArr[i][j] = int(b[lenb-1-j])
            cnt[j]+=binArr[i][j]
    ans=[0]*60
    answer = 0
    for i in range(n):
        for j in range(60):
            # 1: cnt[j]
            # 0: n-cnt[j]
            cnt[j]-=binArr[i][j]
            if binArr[i][j] == 0:
                ans[j] += cnt[j]
            else:
                ans[j] += (n-cnt[j]-i-1)
    x=1
    for i in range(60):
        answer += ans[i]*x
        answer %= mod
        x*=2
        x%=mod
    print(answer)
    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------
### BUGGY CODE ###

import copy

N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]

min_w_per_v = [10**11] * (10**6)
min_w_per_v[0] = 0

for i in range(N):
    w, v = wv[i]
    tmp = copy.deepcopy(min_w_per_v)
    for j in range(v, len(min_w_per_v)):
        min_w_per_v[j] = min(tmp[j], tmp[j-v]+w)
        
for n, i in enumerate(min_w_per_v[::-1]):
    if i <= W:
        print(10**6-n-1)
        break

### FIXED CODE ###

import copy

N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]

min_w_per_v = [10**11] * (10**5+3)
min_w_per_v[0] = 0

for i in range(N):
    w, v = wv[i]
    tmp = copy.deepcopy(min_w_per_v)
    for j in range(v, len(min_w_per_v)):
        min_w_per_v[j] = min(tmp[j], tmp[j-v]+w)
        
for n, i in enumerate(min_w_per_v[::-1]):
    if i <= W:
        print(10**5+3-n-1)
        break
### BUGGY CODE ###

L = raw_input()
L = L.split()
count = 0
for i, val in enumerate(L):
    L[i] = int(val)
while (L[0] > 0) | (L[1] > 0):
    if L[2] > 0:
        if L[0] > 0:
            L[0] -= 1
            count += 1
        else:
            L[1] -= 1
            count += 2
        L[2] -= 1
    else:
        L[0] = 0
        L[1] -= 1
        count += 1
if L[2] > 0:
    count += 1
print(count)




### FIXED CODE ###

L = raw_input()
L = L.split()
count = 0
for i, val in enumerate(L):
    L[i] = int(val)
sum = L[0] + L[1]
if sum < L[2]-1:
    count = L[0] + 2*L[1] + 1
else:
    count = L[2] + L[1]
print(count)
### BUGGY CODE ###

import numpy as np

x, move, d = map(int, input().split())

for k in range(move):
    move_plus = x + d
    move_minus = x - d

    if abs(move_plus) > abs(move_minus):
        x = move_minus
    else:
        x = move_plus

    if abs(x) <= d/2 and (move-(k+1))%2==0:
        break
    elif abs(x) <= d/2 and (move-(k+1))%2!=0:
        if np.sign(x) == 1 or np.sign(x) == 0:
            x = x-d
        else:
            x = x+d

        break

print(abs(x))


### FIXED CODE ###

import numpy as np

x, move, d = map(int, input().split())

num = int(abs(x)/d)
ans = 0

if move <= num:
    if np.sign(x) == 1:
        ans = x-d*move
    else:
        ans = x+d*move

elif (move-num)%2==0:
    if np.sign(x) == 1:
        ans = x-d*num
    else:
        ans = x+d*num

elif (move-num)%2!=0:
    if np.sign(x) == 1:
        ans = x-d*(num+1)
    else:
        ans = x+d*(num+1)


print(abs(ans))
### BUGGY CODE ###

import itertools
from collections import Counter


def main():
    N, M = map(int, input().split())
    LR = []
    for _ in range(M):
        L, R = map(int, input().split())
        LR.append(list(range(L, R + 1)))
    LR = list(itertools.chain.from_iterable(LR))
    C = Counter(LR)

    ans = 0
    for c in C.values():
        if c == M:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N, M = map(int, input().split())
    L = 0
    R = N
    for _ in range(M):
        l, r = map(int, input().split())
        if L < l:
            L = l
        if R > r:
            R = r
    ans = 0
    if L <= R:
        ans = R - L + 1
    print(ans)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

n=int(input())
Alist=[0]+[int(input()) for i in range(n)]

now=1
count=0
Hist=[]

while now!=2:
    now=Alist[now]
    count+=1
    if now in Hist:
        count=-1
        break
    Hist.append(now)
print(count)

### FIXED CODE ###

n=int(input())
Alist=[0]+[int(input()) for i in range(n)]

now=1
count=0

for _ in range(n):
    now=Alist[now]
    count+=1
    if now==2:
        print(count)
        exit()
print(-1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import copy
def main():
    N = int(input())
    A = [int(input()) for i in range(N)]
    for i in range(N):
        Ap = copy.copy(A)
        del Ap[i]
        print(max(Ap))
if __name__ == '__main__':
    main()

### FIXED CODE ###

# -*- coding: utf-8 -*-
import copy
def main():
    N = int(input())
    A = [int(input()) for i in range(N)]
    Am = max(A)
    if A.count(Am)>1:
        for j in range(N):
            print(Am)
        return
    Ap = copy.copy(A)
    set(Ap)
    Ap.sort(reverse=True)
    for i in range(N):
        if  A[i] != Am:
            print(Am)
        else:
            print(Ap[1])
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n,W=map(int,input().split())
w_list=[]
v_list=[]
for i in range(n):
    w,v=map(int,input().split())
    w_list.append(w)
    v_list.append(v)
dp={}
def f(i,w):
    if (i,w) in dp:
        return dp[(i,w)]
    else:
        if i==n:
            return 0
        else:
            if w_list[i]<=w:
                a=max(f(i+1,w),f(i+1,w-w_list[i])+v_list[i])
            else:
                a=f(i+1,w)
            dp[(i,w)]=a
            return a
print(f(0,W))




### FIXED CODE ###

n,W=map(int,input().split())
w_list=[]
v_list=[]
dp=[]
for i in range(n):
    w,v=map(int,input().split())
    w_list.append(w)
    v_list.append(v)
for i in range(n):
    dp_sub=[]
    for j in range(W+1):
        dp_sub.append(-1)
    dp.append(dp_sub)
dp_sub=[]
for j in range(W+1):
    dp_sub.append(0)
dp.append(dp_sub)
for i in range(n):
    i_=n-1-i
    for j in range(W+1):
        if w_list[i_]<=j:
            dp[i_][j]=max(dp[i_+1][j],dp[i_+1][j-w_list[i_]]+v_list[i_])
        else:
            dp[i_][j]=dp[i_+1][j]
print(dp[0][W])
### BUGGY CODE ###

S = input()


MOD = 10**9 + 7



# time complexity: O(|S|)
def focus_on_B():
    cuml = [[0] * 3 for _ in range(len(S))]
    num_A = num_C = num_q = 0
    for i, char in enumerate(S):
        if char == "A":
            num_A += 1
        elif char == "C":
            num_C += 1
        elif char == "?":
            num_q += 1
        cuml[i][0] = num_A
        cuml[i][1] = num_C
        cuml[i][2] = num_q

    num_combinations = 0
    for i in range(1, len(S) - 1):
        if S[i] in {"B", "?"}:
            A_L = cuml[i-1][0]
            Q_L = cuml[i-1][2]
            C_R = cuml[-1][1] - cuml[i][1]
            Q_R = cuml[-1][2] - cuml[i][2]
            left_pow = 3**Q_L
            right_pow = 3**Q_R
            num_combinations += (A_L * left_pow + Q_L * left_pow//3) * (C_R * right_pow + Q_R * right_pow//3)
            num_combinations %= MOD
        else:
            continue
    print(num_combinations)

focus_on_B()


### FIXED CODE ###

S = input()

MOD = 10**9 + 7
dp = [[0] * 4 for _ in range(len(S) + 1)]
dp[len(S)][3] = 1
for i in range(len(S))[::-1]:
    dp[i][3] = 3 * dp[i + 1][3] if S[i] == "?" else dp[i + 1][3]
    dp[i][3] %= MOD
    if S[i] == "?":
        dp[i][0] = (3 * dp[i + 1][0] + dp[i + 1][1]) % MOD
        dp[i][1] = (3 * dp[i + 1][1] + dp[i + 1][2]) % MOD
        dp[i][2] = (3 * dp[i + 1][2] + dp[i + 1][3]) % MOD
    else:
        dp[i][0] = (dp[i + 1][0] + int(S[i] == "A") * dp[i + 1][1]) % MOD
        dp[i][1] = (dp[i + 1][1] + int(S[i] == "B") * dp[i + 1][2]) % MOD
        dp[i][2] = (dp[i + 1][2] + int(S[i] == "C") * dp[i + 1][3]) % MOD
print(dp[0][0])
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import re

text = input()
pattern = 'ST'

while True:
    if pattern in text:
        splt_txt = re.split(pattern, text)
        text = ''.join(splt_txt)
    else:
        break

print(len(text))


### FIXED CODE ###

# -*- coding: utf-8 -*-

text = list(input())
txt_stuck = []

for i in text:
    if i == 'S':
        txt_stuck.append(i)
    elif i == 'T' and txt_stuck == []:
        txt_stuck.append(i)
    elif i == 'T' and txt_stuck[-1] == 'T':
        txt_stuck.append(i)
    elif i == 'T' and txt_stuck[-1] == 'S':
        txt_stuck.pop()

print(len(txt_stuck))
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]

b = set(a)
c = []
for i in b:
  c.append([i, a.count(i)])

t = []
for j in range(len(c)):
  total = 0
  total += c[j][1]
  
  if c[j][0]-1 in a:
    total += c[j-1][1]
  
  if c[j][0]+1 in a:
    total += c[j+1][1]

  t.append(total)

print(max(t))

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = [0] * (int(1e5)+5)
for i in range(n):
    ans[a[i]-1] += 1
    ans[a[i]] += 1
    ans[a[i]+1] += 1
print(max(ans))
### BUGGY CODE ###

n = int(input())
a = input().split(" ")

flag = False
for i in range(n-1):
    for j in range(i+1, n):
        if a[i] == a[j]:
            flag = True
            break
    if flag:
        break

print('NO' if flag else 'YES')


### FIXED CODE ###

n = int(input())
a = input().split(" ")

a.sort()
flag = False
for i in range(n-1):
    if a[i] == a[i+1]:
        flag = True
        break

print('NO' if flag else 'YES')
### BUGGY CODE ###

t = input()
ans = []

for i in range(len(t) - 1, -1, -1):
    if t[i] == '?' and i == len(t) - 1:
        ans.insert(0, 'D')
        continue
    if t[i] == '?':
        if ans[0] == 'D':
            ans.insert(0, 'P')
        else:
            ans.insert(0, 'D')
    else:
        ans.insert(0, t[i])

print(''.join(ans))


### FIXED CODE ###

t = input()
ans = []

for i in range(len(t)):
    ans.append(t[i])

for i in range(len(t)):
    if ans[i] == '?':
        ans[i] = 'D'
print(''.join(ans))