Harryxun/stf_run huggingface dataset:
BASE = ['A', 'T', 'C', 'G']

N, Q = map(int, input().split())
S = input()
l = [None] * N
r = [None] * N
for i in range(Q):
    l[i], r[i] = map(int, input().split())
    l[i] -= 1
    r[i] -= 1

cumsum = [0] * N
sumbgn = [0] * N
sumend = [0] * N
tmpsum = 0
for i in range(1, N):
    if S[i-1:i+1] == 'AC':
        sumbgn[i-1] = sumbgn[i-2] + 1 if i-2 >= 0 else 1
        sumend[i] = sumend[i-1] + 1
    else:
        sumbgn[i-1] = sumbgn[i-2] if i-2 >= 0 else 0
        sumend[i] = sumend[i-1]

for i in range(Q):
    sumr = sumend[r[i]]
    suml = sumbgn[l[i]-1] if l[i] > 0 else 0
    print(sumr - suml)

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
l = [None] * Q
r = [None] * Q
for i in range(Q):
    l[i], r[i] = map(int, input().split())
    l[i] -= 1
    r[i] -= 1

sumbgn = [0] * N
sumend = [0] * N
for i in range(1, N):
    if S[i-1:i+1] == 'AC':
        sumbgn[i-1] = sumbgn[i-2] + 1 if i-2 >= 0 else 1
        sumend[i] = sumend[i-1] + 1
    else:
        sumbgn[i-1] = sumbgn[i-2] if i-2 >= 0 else 0
        sumend[i] = sumend[i-1]

for i in range(Q):
    sumr = sumend[r[i]]
    suml = sumbgn[l[i]-1] if l[i] > 0 else 0
    print(sumr - suml)
from itertools import permutations
n = int(input())
P = list(map(int,input().split()))
Q = list(map(int,input().split()))

A = [i+1 for i in range(n)]



for i,per in enumerate(list(permutations(A))):
  if per == P:
    x = i
  if per == Q:
    y = i
  
print(abs(x-y))


### FIXED CODE ###

from itertools import permutations
n = int(input())
p = tuple(map(int,input().split()))
q = tuple(map(int,input().split()))

a = [i+1 for i in range(n)]
for i,per in enumerate(list(permutations(a))):
    if per == p:
        x = i
    if per == q:
        y = i
print(abs(x-y))
a, b = map(int, input().split())
if a > b:
    print("GREATER")
elif a < b:
    print("LESS")
else:
    print("EQUAL")

### FIXED CODE ###

a = int(input())
b = int(input())
if a > b:
    print("GREATER")
elif a < b:
    print("LESS")
else:
    print("EQUAL")
N,M=map(int,raw_input().split(' '))

g=[[False for i in range(N)] for j in range(N)]
ab=[()]*N
v=[False]*N

def dfs(n):
    v[n]=True
    for i in range(N):
        if g[n][i]==True and v[i]==False:
            dfs(i)

for i in range(M):
    a,b=map(int,raw_input().split(' '))
    a-=1
    b-=1
    g[a][b]=g[b][a]=True
    ab[i]=(a,b)

ans=0
for i in range(M):
    a,b=ab[i]
    g[a][b]=g[b][a]=False

    dfs(0)

    if v!=[True]*N:
        ans+=1

    g[a][b]=g[b][a]=True
    v=[False]*N

print ans



### FIXED CODE ###

N,M=map(int,raw_input().split(' '))

g=[[False for i in range(N)] for j in range(N)]
ab=[()]*M
v=[False]*N

def dfs(n):
    v[n]=True
    for i in range(N):
        if g[n][i]==True and v[i]==False:
            dfs(i)

for i in range(M):
    a,b=map(int,raw_input().split(' '))
    a-=1
    b-=1
    g[a][b]=g[b][a]=True
    ab[i]=(a,b)

ans=0
for i in range(M):
    a,b=ab[i]
    g[a][b]=g[b][a]=False

    dfs(0)

    if v!=[True]*N:
        ans+=1

    g[a][b]=g[b][a]=True
    v=[False]*N

print ans
import math as m

A, B = list(map(int, input().split()))
#A , B = 12, 18
def lcm(a, b):
    return (A * B) // m.gcd(A, B)

def sieve_of_eratosthenes(n): # n以下の素因数を求める
    candidate = [1 for i in range(n+1)]
    candidate[0:2] = [0 , 0]
    for i in range(len(candidate)):
        if (candidate[i] == 0):
            continue
        j = 2
        while j * i < len(candidate):
            candidate[i * j] = 0
            j = j + 1
    primes = [i for i in range(n) if candidate[i] == 1]
    return primes

def prime_factorize(A):
    p = sieve_of_eratosthenes(A)
    a = [0 for i in p]
    for i in range(len(p)):
        if A % p[i] != 0:
            a[i] = 0
        else:
            temp = A
            while temp % p[i] == 0:
                temp = temp / p[i]
                a[i] = a[i] + 1
    return a

pf = prime_factorize(m.gcd(A, B))
num = 1

for x in pf:
    if x >= 1:
        num = num + 1

print(num)


### FIXED CODE ###

import math as m
import fractions

A, B = list(map(int, input().split()))
#A , B = 12, 18

def sieve_of_eratosthenes(n):
    candidate = [1 for i in range(n+1)]
    candidate[0] = 0
    candidate[1] = 0
    for i in range(len(candidate)):
        if (candidate[i] == 0):
            continue
        j = 2
        while j * i < len(candidate):
            candidate[i * j] = 0
            j = j + 1
    primes = [i for i in range(n) if candidate[i] == 1]
    return primes

def prime_factorize(A):
    p = sieve_of_eratosthenes(m.floor(A**0.5))
    a = [0 for i in p]
    for i in range(len(p)):
        if A % p[i] != 0:
            a[i] = 0
        else:
            temp = A
            while temp % p[i] == 0:
                temp = temp / p[i]
                a[i] = a[i] + 1
    return a

#pf = prime_factorize(fractions.gcd(A, B))
# num = 1

# for x in pf:
#     if x >= 1:
#         num = num + 1



# print(num)

g = fractions.gcd(A,B)
primes = []
num = 1

if True:
    i = 2
    while i * i <= g:
        if (g % i == 0):
            cnt = 0
            while g % i == 0:
                cnt = cnt + 1
                g = g // i
            primes.append([i, cnt])
        i = i + 1
    if (g != 1):
        primes.append([g, 1])
print(len(primes)+1)
str = "CODEFESTIVAL2016"
s =input()
cnt = 0
for i in range(16):
  if s[i]!=str[i]:
    cnt++
print(cnt)

### FIXED CODE ###

str = "CODEFESTIVAL2016"
s =input()
cnt = 0
for i in range(16):
  if s[i]!=str[i]:
    cnt+=1
print(cnt)
s=input()
ans=""
for b in s:
    if b=="1":
        ans+="1"
    elif b=="0":
        ans+="0"
    else:
        if len(ans)!=0:
            ans[-1]=""
print(ans)

### FIXED CODE ###

s=input()
ans=""
for b in s:
    if b=="1":
        ans+="1"
    elif b=="0":
        ans+="0"
    else:
        if len(ans)!=0:
            ans = ans[:-1]
print(ans)
n = int(input())
s = input()

ans = 0
for a in range(0,n-2):
    for b in range(a,n-1):
        e = b-a
        #if s[a]!=s[b]:
            for c in range(b,n):
                f = c-b
                if e!=f:
                    if s[a]!=s[c] and s[b]!=s[c] and s[a]!=s[b]:
                        ans += 1

print(ans)

### FIXED CODE ###

n = int(input())
s = input()

r = s.count("R")
g = s.count("G")
b = s.count("B")
ans = r*g*b

for i in range(n):
    for j in range(1,n//2+1):
        if i+2*j>=n:
            break
        
        if s[i]!=s[i+j] and s[i+j]!=s[i+2*j] and s[i]!=s[i+2*j]:
            ans -= 1
print(ans)
N, W = (int(i) for i in input().split())
w = [0]*N
v = [0]*N
for i in range(N):
  w[i], v[i] = (int(j) for j in input().split())
w0 = w[0]
wh = [a - w0 for a in w]
dp = [[[-1]*(N+1) for i in range(3*N+1)] for j in range(N+1)]
dp[0][0][0] = 0
for i in range(N):
  for j in range(3*N+1):
    for k in range(N+1):
      if dp[i][j][k] != -1:
        dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k])
      if j - wh[i] >=0 and k-1 >=0 and dp[i][j-wh[i]][k-1] != -1:
        dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j-wh[i]][k-1]+v[i])
res = 0
for j in range(3*N+1):
  for k in range(N+1)
  	if j + w0*k <= W:
      res = max(dp[N][j][k], res)
print(res)

### FIXED CODE ###

N, W = (int(i) for i in input().split())
w = [0]*N
v = [0]*N
for i in range(N):
  w[i], v[i] = (int(j) for j in input().split())
w0 = w[0]
wh = [a - w0 for a in w]
dp = [[[-1]*(N+1) for i in range(3*N+1)] for j in range(N+1)]
dp[0][0][0] = 0
for i in range(N):
  for j in range(3*N+1):
    for k in range(N+1):
      if dp[i][j][k] != -1:
        dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k])
      if j - wh[i] >=0 and k-1 >=0 and dp[i][j-wh[i]][k-1] != -1:
        dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j-wh[i]][k-1]+v[i])
res = 0
for j in range(3*N+1):
  for k in range(N+1):
    if j + w0*k <= W:
      res = max(dp[N][j][k], res)
print(res)
N,A,B = map(int,input().split())
mod = 10**9+7
X = 200000
inv_t = [0]+[1]
for i in range(2,X):
  inv_t += [inv_t[mod % i] * (mod - int(mod / i)) % mod]

def fast_mod_pow(x, n, mod):
    r = 1
    while n>0:
        if n&1:
            r = (r * x) % mod
        x = (x * x) % mod
        n >>= 1
    return r

def comb(n,k):
    value = 1
    for i in range(n-k+1,n+1):
        value *= i
        value %= mod
    for i in range(1,k+1):
        value *= inv_t[i]
        value %= mod
    return value

ans = fast_mod_pow(2,N,mod)-1
ans -= comb(N,A)
ans -= comb(N,B)
print(ans%mod)

### FIXED CODE ###

N,A,B = map(int,input().split())
mod = 10**9+7
X = 210000
inv_t = [0]+[1]
for i in range(2,X):
  inv_t += [inv_t[mod % i] * (mod - int(mod / i)) % mod]

def fast_mod_pow(x, n, mod):
    r = 1
    while n>0:
        if n&1:
            r = (r * x) % mod
        x = (x * x) % mod
        n >>= 1
    return r

def comb(n,k):
    value = 1
    for i in range(n-k+1,n+1):
        value *= i
        value %= mod
    for i in range(1,k+1):
        value *= inv_t[i]
        value %= mod
    return value

ans = fast_mod_pow(2,N,mod)-1
ans -= comb(N,A)
ans -= comb(N,B)
print(ans%mod)
c = map(str,input().split())
if c == "a" or c == "e" or c == "i" or c == "o" or c == "u":
  print(vowel)
else:
  print(consonant)

### FIXED CODE ###

c = input()
l = ["a","e","i","o","u"]
if c in l:
  print("vowel")
else:
  print("consonant")
import sympy

num = int(input())
a = list(map(int, input().split()))
b = 0
for i in a:
  for f in sympy.divisors(i)[:-1]:
    if f in a:
      b += 1
      break
print(num - b)  

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
a.sort()
dp = [0] * a[-1]
c = Counter(a)
for i in a:
    for j in range(i, a[-1]+1, i):
        dp[j-1] += 1
ans = 0
for i in a:
    if dp[i-1] == 1 and c[i]:
        ans += 1
print(ans)
def main():
    a, b, c, d, e, f = map(int, input().split())

    maxConcentration = 0

    for i in range(31):
        for j in range(i + 1, (29 * a // b) + 1):
            water = (i * a + j * b) * 100
            possibleSugar = int(min(f - water, water * e / 100))
            for k in range((possibleSugar // c) + 1):
                for l in range(((possibleSugar - k * c) // d) + 1):
                    sugar = k * c + l * d

                    if water + sugar > f:
                        break

                    if water + sugar == 0:
                        continue

                    concentration = 100 * sugar / (water + sugar)

                    if concentration > maxConcentration:
                        maxConcentration = concentration
                        resSugarWater = water + sugar
                        resSugar = sugar
    
    print(resSugarWater, resSugar)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    a, b, c, d, e, f = map(int, input().split())

    maxConcentration = 0
    resSugarWater = 0
    resSugar = 0

    for i in range(31):
        for j in range((29 * a * i // b) + 1):
            water = (i * a + j * b) * 100
            possibleSugar = int(min(f - water, water * e / 100))
            for k in range((possibleSugar // c) + 1):
                for l in range(((possibleSugar - k * c) // d) + 1):
                    sugar = k * c + l * d

                    if water + sugar > f:
                        break

                    if water + sugar == 0:
                        continue

                    concentration = 100 * sugar / (water + sugar)

                    if concentration >= maxConcentration:
                        maxConcentration = concentration
                        resSugarWater = water + sugar
                        resSugar = sugar
    
    print(resSugarWater, resSugar)

if __name__ == '__main__':
    main()
# -*- coding: utf-8 -*-
import sys
from functools import lru_cache
sys.setrecursionlimit(10**6)
readline = sys.stdin.buffer.readline


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))



@lru_cache(maxsize=None)
def f(c1, c2, c3):
    # if memo[c1][c2][c3] != -1:
    #     return memo[c1][c2][c3]
    c0 = N - (c1 + c2 + c3)
    p0 = c0 / N
    ip0 = 1 - p0
    ret = 1 / ip0
    if c1 > 0:
        p1 = c1 / N
        ret += f(c1-1, c2, c3) * p1 / ip0
    if c2 > 0:
        p2 = c2 / N
        ret += f(c1+1, c2-1, c3) * p2 / ip0
    if c3 > 0:
        p3 = c3 / N
        ret += f(c1, c2+1, c3-1) * p3 / ip0
    # memo[c1][c2][c3] = ret
    return ret


N = read_int()
A = read_int_n()
# memo = [[[-1] * (N + 1) for _ in range(N + 1)] for _ in range(N + 1)]
# memo[0][0][0] = 0
print(f(A.count(1), A.count(2), A.count(3)))


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.buffer.readline


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def f(c1, c2, c3):
    if memo[c1][c2][c3] != -1:
        return memo[c1][c2][c3]
    c0 = N - (c1 + c2 + c3)
    p0 = c0 / N
    ip0 = 1 - p0
    ret = 1 / ip0
    if c1 > 0:
        p1 = c1 / N
        ret += f(c1-1, c2, c3) * p1 / ip0
    if c2 > 0:
        p2 = c2 / N
        ret += f(c1+1, c2-1, c3) * p2 / ip0
    if c3 > 0:
        p3 = c3 / N
        ret += f(c1, c2+1, c3-1) * p3 / ip0
    memo[c1][c2][c3] = ret
    return ret


N = read_int()
A = read_int_n()
memo = [[[-1] * (N + 1) for _ in range(N + 1)] for _ in range(N + 1)]
memo[0][0][0] = 0
print(f(A.count(1), A.count(2), A.count(3)))
n = int(input())
s, t = input().split(
ans = ""
for i, j in zip(s, t):
    ans += i + j
print(ans)

### FIXED CODE ###

n = int(input())
s, t = input().split()
ans = ""
for i, j in zip(s, t):
    ans += i + j
print(ans)
def main():
    S = list(input())
    k = 0
    ans = False
    while True :
        if k == len(S):
            ans = True
            break
        elif S[k] + S[ k + 1] != "hi":
            break
        else :
            k += 2
    if ans : print("Yes")
    else: print("No")
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    S = list(input())
    k = 0
    ans = False
    
    while True :
        if len(S) % 2 != 0 :
            break 
        elif k == len(S):
            ans = True
            break
        elif S[k] + S[ k + 1] != "hi":
            break
        else :
            k += 2
    if ans : print("Yes")
    else: print("No")
if __name__ == '__main__':
    main()
def main():
    a, b, m = map(int, input().split())
    priceOfMicrowaves = list(map(int, input().split()))
    priceOfRefrigerators = list(map(int, input().split()))
    priceTable = [list(map(int,input().split())) for i in range(m)]
    cheepest = priceOfMicrowaves[0] + priceOfRefrigerators[0]
    for price in priceTable:
        if priceOfMicrowaves[price[0]-1] - price[2] >= cheepest:
            continue
        elif priceOfMicrowaves[price[1]-1] - price[2] >= cheepest:
            continue
        if priceOfMicrowaves[price[0]-1]+priceOfRefrigerators[price[1]-1]-price[2] < cheepest:
            cheepest = priceOfMicrowaves[price[0]-1]+priceOfRefrigerators[price[1]-1]-price[2]
    for p in priceOfMicrowaves:
        if p >= cheepest:
            continue
        for q in priceOfRefrigerators:
            if q >= cheepest:
                continue
            if p + q < cheepest:
                cheepest = p + q
    print(cheepest)
    
main()

### FIXED CODE ###

a, b, m = map(int, input().split())
priceOfMicrowaves = list(map(int, input().split()))
priceOfRefrigerators = list(map(int, input().split()))
priceTable = [list(map(int,input().split())) for i in range(m)]
cheepest = priceOfMicrowaves[0] + priceOfRefrigerators[0]
for price in priceTable:
    if priceOfMicrowaves[price[0]-1]-price[2] >= cheepest:
        continue
    elif priceOfRefrigerators[price[1]-1]-price[2] >= cheepest:
        continue
    elif priceOfMicrowaves[price[0]-1]+priceOfRefrigerators[price[1]-1]-price[2] < cheepest:
        cheepest = priceOfMicrowaves[price[0]-1]+priceOfRefrigerators[price[1]-1]-price[2]
if cheepest > min(priceOfMicrowaves) + min(priceOfRefrigerators):
    cheepest = min(priceOfMicrowaves) + min(priceOfRefrigerators)
print(cheepest)
n = int(input())
 
if n == 1:
  print("Hello World")
else n == 2:
  a = int(input())
  b = int(input())
  print(A+B)

### FIXED CODE ###

n = int(input())
 
if n == 1:
  print("Hello World")
else:
  a = int(input())
  b = int(input())
  print(a+b)
import itertools
import math
import sys
import heapq
from collections import Counter
from collections import deque
from fractions import gcd
from functools import reduce
INF = 1 << 60
sys.setrecursionlimit(10 ** 6)

#ここから書き始める
def gcd(*numbers):
    return reduce(gcd, numbers)


n, start = map(int, input().split())
a = list(map(int, input().split()))
gap = []
a.append(start)
a.sort()
for i in range(1, n + 1):
    gap.append(abs(a[i] - a[i - 1]))
# print(gap)
print(gcd(*gap))

### FIXED CODE ###

import itertools
import math
import sys
from collections import Counter
from fractions import gcd
from functools import reduce

n, start = map(int, input().split())
x = list(map(int, input().split()))
x.append(start)
x.sort()
# print(x)
gaps = []
for i in range(n):
    gaps.append(x[i + 1] - x[i])
# print(gaps)
if len(gaps) == 1:
    print(gaps[0])
else:
    ans = reduce(gcd, gaps)
    print(ans)
S = input()
T = input()

if len(T)-len(S) == 1:
  print(Yes)
else:
  print(No)

### FIXED CODE ###

S = input()
T = input()
T.rstrip()
 
if T[:-1] == S:
  print('Yes')
else:
  print('No')
N = int(input())
T,A = map(int,input().split())
H = list(map(int,input().split()) 
tmp=10**3
ans=0
for i in range(N):
    if abs(A-T+H[i]*0.006)<tmp:
        tmp=abs(A-T+H[i]*0.006)
        ans=i+1
print(ans)

### FIXED CODE ###

N = int(input())
T,A = map(int,input().split())
H = list(map(int,input().split()))
tmp = 1000
ans = 0
for i in range(N):
    if abs(A-T+H[i]*0.006)<tmp:
        tmp=abs(A-T+H[i]*0.006)
        ans=i+1
print(ans)
a,b = map(int,input().split())
     
    if a > 9 or b > 9:
      print(-1)
    else:
      out = a * b
      print('{0}'.format(out))

### FIXED CODE ###

a,b = map(int,input().split())

if a > 9 or b > 9:
	print("-1")
else:
	out = a * b
	print('{0}'.format(out))
n = int(input())
a = list(map(int,input().split()))

def solve(a):
    print(a)
    for i in range(n):
        if a[i] != 0:
            break
        if i == n-1:
            return True

    for i in range(n):
        b = []
        for j in range(n):
            if a[j] < 0:
                return False
            c = a[(i+j)%n]-j-1
            b.append(c)

        if solve(b):
            return True

if solve(a):
    print('YES')
else:
    print('NO')

### FIXED CODE ###

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

if sum(a) % (n*(n+1)//2) != 0:
    print('NO')
    exit()
else:
    k = sum(a)// (n*(n+1)//2)


for i in range(n-1):
    d = a[i+1] - a[i] - k

    if d > 0 or d % n != 0:
        print('NO')
        exit()

print('YES')
r = int(input())
sum = 0
for i in range(n):
  sum += i+1
print(sum)

### FIXED CODE ###

n = int(input())
sum = 0
for i in range(n):
  sum += i+1
print(sum)
S = str(input)
alpha = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']

S.sort()
n = 0
m = 0

for i in range(len(S)):
	if S[n] not in alpha:
		print(S[n])
		break
	n += 1

	if n = len(S) - 1:
		m = 1

if m == 1:
	print('None')

### FIXED CODE ###

S = str(input())
alpha = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']

n = 0

for i in range(26):

	if alpha[n] not in S:
		print(alpha[n])
		break
	if n == 25:
		print("None")
		break
		
	n += 1
n = int(raw_input())
his = map(int, raw_input().split(' '))
j,pv,count = 0, -float('inf'),0
while(j < len(his)):
	if pv >= his[j]:
		count +=1
	else:
		count = 1
	m = max(count,m)
	pv = hist[j]
	j +=1
print m

### FIXED CODE ###

n = int(raw_input())
his = map(int, raw_input().split(' '))
j = 0
pv = float('inf')
count = 0
m = 0
while(j < len(his)):
	if pv >= his[j]: count +=1
	else: count = 1
	m = max(count-1,m)
	pv = his[j]
	j +=1
print m
a = int(input())
b = int(input())
c = int(input())
cond = int(input())

count = 0
for i in range(a+1):
    for j in range(b+1):
      for k in range(c+1):
	  	  res = 500 * i + 100 * j + 50 * k
          if(res == cond):
            count = count + 1
print(count)

### FIXED CODE ###

a = int(input())
b = int(input())
c = int(input())
cond = int(input())

count = 0
for i in range(a+1):
    for j in range(b+1):
        for k in range(c+1):
            res = 500 * i + 100 * j + 50 * k
            if(res == cond):
                count = count + 1
print(count)
import sys
sys.setrecursionlimit(1000000)
 
N,M = map(int,input().split())
A = list(map(int,input().split()))

BC =  [[int(i) for i in input().split()] for M in range(M)]



A.sort()
#BC.sort()
BC = sorted(BC, key=lambda x:x[1])
BC.reverse()

now = 0
end = 0

for i in range(M):
    for j in range(BC[i][0]):
        if A[now+j] < BC[i][1]:
            A[now+j] = BC[i][1]
        else:
            end = 1
            break
    
    if end == 1:
        break
    now = now + BC[i][0]

print(sum(A))

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
 
N,M = map(int,input().split())
A = list(map(int,input().split()))

BC =  [[int(i) for i in input().split()] for M in range(M)]



A.sort()
#BC.sort()
BC = sorted(BC, key=lambda x:x[1])
BC.reverse()

now = 0
end = 0

for i in range(M):
    for j in range(BC[i][0]):
        if now+j >= N:
            end = 1
            break
        if A[now+j] < BC[i][1]:
            A[now+j] = BC[i][1]
        else:
            end = 1
            break
    
    if end == 1:
        break
    now = now + BC[i][0]

print(sum(A))
x = int(input())
 
for val in range(x, x**1000) :
	if x ==2 :
		print(x)
		break
	elif ((10** (val-1)) % val) == 1 :
		print (val)
		break
	else :
		continue

### FIXED CODE ###

S, T = (str(i) for i in input().split())

U = T + S
print(U)
count = int(input())
numbers = map(int, input().split(' '))

counter = 0
while True:
  for item in numbers:
    if item % 2 == 1:
      break
  	else:
      counter += 1
  numbers = [item / 2 for item in numbers]

print(counter)
      

### FIXED CODE ###

count = int(input())
numbers = [int(num) for num in input().split()]

counter = 0
while True:
  tmp = 0
  for item in numbers:
    tmp += item % 2
  if tmp > 0:
    break
  counter += 1
  numbers = [item / 2 for item in numbers]
print(counter)
a = 1
while a != 0:
	a = raw_input()
	print 'Case i: ',a

### FIXED CODE ###

a = int(1)
b = int(1)
while True:
	b = int(raw_input())
	if b != 0:
		print('Case ' + str(a) + ': ' + str(b))
		a += 1
		continue
	else:
		break
N, M = map(int, input().split())

a = []
b = []
c = []
d = []

for i in range(N):
    x, y = map(int, input().split())
    a.append(x)
    b.append(y)

for j in range(M):
    x, y = map(int, input().split())
    c.append(x)
    d.append(y)

for i in range(N):
    minDist = 10**8 * 2
    for j in range(M):
        dist = abs(c[j]-a[i]) + abs(d[j]-b[i]) 
        if dist < minDist:
            minDist = dist
            ans = j
        
    print(ans+1)


### FIXED CODE ###

N, M = map(int, input().split())

a = []
b = []
c = []
d = []

for i in range(N):
    x, y = map(int, input().split())
    a.append(x)
    b.append(y)

for j in range(M):
    x, y = map(int, input().split())
    c.append(x)
    d.append(y)

for i in range(N):
    ans = 0
    minDist = 10**8 * 2
    for j in range(M):
        dist = abs(c[j]-a[i]) + abs(d[j]-b[i]) 
        if dist < minDist:
            minDist = dist
            ans = j
        
    print(ans+1)
@parallel
@roles('allgame')
def _last_redis_save():
	with cd(get_deploy_path()):
		redisSet = set()
		ret = run('supervisorctl status')
		for line in ret.split('\n'):
			line = line.strip()
			if line.find('RUNNING') >= 0 and line.find('redis') >= 0:
				name = line.split()[0].strip()
				redisSet.add(name)

		ret = []
		with cd('db'):
			for redis in sorted(list(redisSet)):
				port = redis[5:]
				ret.append(run('ls -l -h game%s.rdb' % port))
		return '\n'.join(ret)

def last_redis_save():
	result = execute(_last_redis_save)
	for k in sorted(result.keys()):
		print '-'*20
		print k, ':'
		v = result[k]
		print v

### FIXED CODE ###

#!/usr/bin/env python

s = raw_input()

s1 = []
for x in s:
	if not s1:
		s1.append(x)
		continue
	if x == 'T' and s1[-1] == 'S':
		# s1 = s1[:-1]
		del s1[-1]
	else:
		s1.append(x)

print len(s1)