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

from collections import deque

h,w=map(int,input().split())
cy,cx=map(int,input().split())
gy,gx=map(int,input().split())
inf=float('inf')
maze=[]
for _ in range(h):
  s=list(input())
  for i in range(w):
    if s[i]=='.':
      s[i]=inf
  maze.append(s)
  
def solve(maze,cy,cx,gy,gx):
  [sy,sx]=[cy-1,cx-1]
  qu=deque([[sy,sx]])
  maze[sy][sx]=0
  T=0
  while qu:
    y,x=qu.popleft()
    t=maze[y][x]
      
    for i in ([1,0],[0,1],[-1,0],[0,-1]):
      ny=y-i[0]
      nx=x-i[1]
      if 0<=ny<=h-1 and 0<=nx<=w-1 and maze[ny][nx]!='#':
        if maze[ny][nx]>t:
          maze[ny][nx]=t
          qu.appendleft([ny,nx])
    for j in range(-2,3):
      for k in range(-2,3):
        ny=y-j
        nx=x-k
        if 0<=ny<=h-1 and 0<=nx<=w-1 and maze[ny][nx]!='#':
          if maze[ny][nx]>t:
            maze[ny][nx]=t+1
            qu.append([ny,nx])
            
  return maze[gy-1][gx-1]
  
if solve(maze,cy,cx,gy,gx)==inf:
  print(-1)
  
else:
  print(solve(maze,cy,cx,gy,gx))
    
  

### FIXED CODE ###

from collections import deque
import copy

h,w=map(int,input().split())
cy,cx=map(int,input().split())
gy,gx=map(int,input().split())
inf=float('inf')
maze=[]
for _ in range(h):
  s=list(input())
  for i in range(w):
    if s[i]=='.':
      s[i]=inf
  maze.append(s)
  
def solve(maze,cy,cx,gy,gx):
  maze1=copy.deepcopy(maze)
  [sy,sx]=[cy-1,cx-1]
  qu=deque([[sy,sx]])
  maze[sy][sx]=0
  T=0
  while qu:
    y,x=qu.popleft()
    t=maze[y][x]
    
    if maze1[y][x]!=1:
      
      for i in ([1,0],[0,1],[-1,0],[0,-1]):
        ny=y-i[0]
        nx=x-i[1]
        if 0<=ny<=h-1 and 0<=nx<=w-1 and maze[ny][nx]!='#':
          if maze[ny][nx]>t:
            maze[ny][nx]=t
            qu.appendleft([ny,nx])
          
      
      for j in range(-2,3):
        for k in range(-2,3):
          ny=y-j
          nx=x-k
          if 0<=ny<=h-1 and 0<=nx<=w-1 and maze[ny][nx]!='#':
            if maze[ny][nx]>t:
              maze[ny][nx]=t+1
              qu.append([ny,nx])
      maze1[y][x]=1
            
  return maze[gy-1][gx-1]
  
if solve(maze,cy,cx,gy,gx)==inf:
  print(-1)
  
else:
  print(solve(maze,cy,cx,gy,gx))
### BUGGY CODE ###

def fib(n):
    return 1 if n == 0 or n == 1 else fib(n - 1) + fib(n - 2)

print(fib(int(input())))

### FIXED CODE ###

def fib(n):
    n1 = n2 = tmp = 1
    for _ in range(n - 1):
        tmp = n1 + n2
        n1, n2 = n2, tmp
    return tmp

print(fib(int(input())))
### BUGGY CODE ###

import numpy as np
n,m = list(map(int,input().split()))
d = [[1<<n] for _ in range(m)]
s = 1<<0
for i in range(m):
  a,b = list(map(int,input().split()))
  d[i] = ((1<<a)-1) ^ ((1<<b)-1)
  s |= d[i]

spr = [[False] for _ in range(m)]

ans = float('inf')
for bit in range(1<<n):
  spr = [True for _ in range(m)]
  if bit & s > 0:
    for k in range(m):
      if (d[k] & bit) > 0:
        spr[k] = False
    if sum(spr) == 0:
      ans = min(ans, sum([1 for i in range(n) if bit & 1<<i]))

print(ans)

### FIXED CODE ###


n,m = list(map(int,input().split()))
d = [0]*m
spr = [True]*m
ma = 0
mi = 0
for i in range(m):
    a,b = list(map(int,input().split()))
    d[i] = [a,b]

d = sorted(d)
pre = d[0][1]
ans = 1
for i,(a,b) in enumerate(d):
  if a < pre:
    if b < pre:
      pre = b
  else:
    ans += 1
    pre = b

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

from scipy.sparse.csgraph import dijkstra
import sys 
input = sys.stdin.readline

def solve():
  n = int(input())
  d = [[float("Inf")]*n for _ in range(n)]
  for i in range(n-1):
    a,b,c = (int(i) for i in input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c
  q,k = (int(i) for i in input().split())
  d = dijkstra(d,indices=k-1)

  for i in range(q):
    x,y = (int(i) for i in input().split())
    print(int(d[x-1] + d[y-1]))

solve()

### FIXED CODE ###


import sys 
input = sys.stdin.readline
from collections import deque
def solve():
  n = int(input())
  d = [[]*n for _ in range(n)]
  for i in range(n-1):
    a,b,c = (int(i) for i in input().split())
    d[a-1].append((b-1,c))
    d[b-1].append((a-1,c))
  q,k = (int(i) for i in input().split())
  #kからの距離を計算する
  d2 = [10**10]*n
  visit = [False]*n
  query = deque([(k-1,0)]) #始点、距離
  while query:
    place,dist = query.pop()
    if visit[place]:
      continue
    else:
      visit[place] = visit
      d2[place] = dist
      for i in range(len(d[place])):
        np,nc = d[place][i]
        if not visit[np]:
          query.append((np,nc+dist))
  for i in range(q):
    x,y = (int(i) for i in input().split())
    print(int(d2[x-1] + d2[y-1]))

solve()
### BUGGY CODE ###

from collections import Counter
n=int(input())
s_=input()
s=Counter(s_)
rgb = s['R'] * s['G'] * s['B']
cnt=0
for i in range(len(s_)):
  for j in range(i+1,len(s_)):
    h=j-i+j
    if h<len(s_):
      if s_[i]!=s_[j] and s_[h]!=s_[j] and s_[i]!=s_[h]:
        cnt+=1

print(rgb-cnt)

### FIXED CODE ###


n=int(input())
s_=input()
r, g, b = s_.count("R"), s_.count("G"), s_.count("B")
rgb = r * g * b
cnt=0
for i in range(len(s_)):
  for j in range(i+1,len(s_)):
    h=j-i+j
    if h<n:
      if s_[i]!=s_[j] and s_[h]!=s_[j] and s_[i]!=s_[h]:
        cnt+=1

print(rgb-cnt)
### BUGGY CODE ###

from fractions import gcd
def main():

    N = int(input())
    a_list = list(map(int, input().split()))

    MOD = 10**9 + 7

    a_lcm = a_list[0]
    for a in a_list[1:]:
        a_lcm *= a // gcd(a,a_lcm)

    res = 0
    for a in a_list:
        res += a_lcm // a
        res %= MOD
    print(res)

if __name__ == "__main__":
    main()

### FIXED CODE ###


from fractions import gcd
def main():

    N = int(input())
    a_list = list(map(int, input().split()))

    MOD = 10**9 + 7

    a_lcm = a_list[0]
    for a in a_list[1:]:
        a_lcm *= a // gcd(a,a_lcm)

    res = 0
    for a in a_list:
        res += a_lcm // a
    print(res%MOD)

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

import numpy as np
import sys
input = sys.stdin.readline

N = int(input())
V = np.array([[int(i) for i in input().split()] for j in range(N)])

dp = np.zeros((N, 3), int)
dp[0] = V[0]
for i in range(1, N):
    dp[i,0] = max(dp[i-1,np.array([1,2])]+V[i,0])
    dp[i,1] = max(dp[i-1,np.array([0,2])]+V[i,1])
    dp[i,2] = max(dp[i-1,np.array([0,1])]+V[i,2])

print(dp[N-1].max())

### FIXED CODE ###

import numpy as np

# 入力
N = int(input())
a = np.array([[int(i) for i in input().split()] for j in range(N)]).T

# a(0行), b(1行), c(2行)の添え字付きDPテーブルを生成
dp = np.zeros(3*(N+1), dtype=int).reshape(3, (N+1))

# 0日目(0)からN-1日目(N-1)までループ処理
for i in range(N):    # 参照する前日(i)
    for j in [0, 1, 2]:    # 前日(i)のアクティビティ
        for k in [0, 1, 2]:    # 当日(i+1)のアクティビティ
            if j != k:    # 前日のアクティビティではいけない
                dp[k, i+1] = max(dp[k, i+1], dp[j, i] + a[j, i])
                
# N日目の処理
ans = 0
for j in [0, 1, 2]:
    ans = max(ans, dp[j, N])
print(ans)
### BUGGY CODE ###


n, y = map(int, input().split())

flg = False

# iは10000円札の枚数、jは5000円札の枚数、kは1000円札の枚数
for i in range(n + 1):
    for j in range(n + 1 - i):
        for k in range(n + 1 - i - j):
            if 10000 * i + 5000 * j + 1000 * k == y and i + j + k == n and not flg:
                flg = True
                print(i, j, k)
        else:
            continue
        break
    else:
        continue
    break

if not flg:
    print(-1, -1, -1)


### FIXED CODE ###


n, y = map(int, input().split())

flg = False

# iは10000円札の枚数、jは5000円札の枚数、kは1000円札の枚数
for i in range(n + 1):
    for j in range(n + 1 - i):
        k = (y - 10000 * i - 5000 * j) // 1000
        if i + j + k == n and not flg:
            flg = True
            print(i, j, k)
            break
    else:
        continue
    break

if not flg:
    print(-1, -1, -1)
### BUGGY CODE ###

N=int(input())
S=input()
a=0
for i in range(1000):
 i1=int(i/100)
 i2=int((i-i1*100)/10)
 i3=i%10
 for j in range(N-2):
  if int(S[j])==i1:
   for k in range(j+1,N-1):
    if int(S[k])==i2:
     for l in range(k+1,N):
      if int(S[l])==i3:
       a+=1
       break
     else:
      continue
     break
   else:
    continue
   break
print(a)


### FIXED CODE ###

N=int(input())
S=input()
A=[0]*N
for i in range(N):
 A[i]=int(S[i])
b=0
for i in range(1000):
 i1=int(i/100)
 i2=int((i-i1*100)/10)
 i3=i%10
 a=0
 for j in range(N):
  if a==0:
   if A[j]==i1:
    a+=1
  elif a==1:
   if A[j]==i2:
    a+=1
  else:
   if A[j]==i3:
    b+=1
    break
print(b)
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
left = []
right = []
for i in range(q):
  l,r = map(int,input().split())
  left.append(l)
  right.append(r)
for j in range(q):
  print(s[left[j]-1:right[j]].count("AC"))

### FIXED CODE ###

n,q = map(int,input().split())
s = input()
left = []
right = []
ans = [0]*(n+1)
for i in range(q):
  l,r = map(int,input().split())
  left.append(l)
  right.append(r)
for j in range(n):
  ans[j+1] = ans[j]+(1 if s[j:j+2]=="AC" else 0) 
for k in range(q):
  print(ans[right[k]-1]-ans[left[k]-1])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
t = 1
a = 10 ** 18

if 0 in A:
    t = 0
else:
    for i in A:
        t *= i

if t > a:
    print("-1")
else:
    print(t)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
t = 1
a = 10 ** 18

if 0 in A:
    t = 0
else:
    for i in A:
        t *= i
        if t > a:
            break

if t > a:
    print("-1")
else:
    print(t)
### BUGGY CODE ###

from numba import jit

@jit
def f(lst):
    for n in range(N):
        L = max(0, n-lst[n])
        R = min(N-1 , n + lst[n])
        B[L] += 1
        if R+1 != N:
            B[R+1] -= 1
    return B     
    
@jit
def f2(lst):
    for i in range(1,N):
        ruiseki[i] = ruiseki[i-1] + lst[i]
    return ruiseki    

N,K,*A = map(int,open(0).read().split())

for k in range(K):
    if all(A) == N:
        break
    B = [0] * N
    B = f(A)
   
    ruiseki = [0] * N
    ruiseki[0] = B[0]
    A = f2(B)
print(*ruiseki,sep=" ")    
   

### FIXED CODE ###

from itertools import accumulate
#from operator import add

N,K = map(int,input().split())
A = map(int,input().split()) 
for k in range(K):
    B = [0] * N
    for i,x in enumerate(A):
        L = max(0, i-x)
        R = min(N-1, i+x)
        B[L] += 1
        if R+1 != N:
            B[R+1] -= 1
    #L = accumulate(B,add) 
    L = list(accumulate(B))[:]
    if L == A:
        break
    A = L
print(*A)
### BUGGY CODE ###

import itertools
N = int(input())
A = [int(_) for _ in input().split()]
cumsum = [0]
for a in A:
    cumsum += [cumsum[-1] + a]
ans = 0
for i, j in itertools.combinations(range(N + 1), 2):
    ans += cumsum[j]-cumsum[i] == 0
print(ans)


### FIXED CODE ###

import heapq
N = int(input())
A = [int(_) for _ in input().split()]
cumsum = [0]
for a in A:
    cumsum += [cumsum[-1] + a]
heapq.heapify(cumsum)
before = 10 ** 10
count = 0
ans = 0
while cumsum:
    now = heapq.heappop(cumsum)
    count += before == now
    if not (before == now and cumsum):
        ans += count * (count + 1) // 2
        count = 0
    before = now
print(ans)
### BUGGY CODE ###

H,N = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
ab = min(AB,key = lambda x:x[1])
INF = float('inf')
dp = [INF]*(H+1)
mi_a = ab[0]
mi_b = ab[1]
dp[0] = 0
for i in range(1,H+1):
  if i<=mi_a:
    dp[i]=mi_b
  else:
    for k in AB:
      a = k[0]
      b = k[1]
      tmp = max(0,i-a)
      dp[i] = min(dp[i],dp[tmp]+b)
    
print(dp[H])

### FIXED CODE ###

H,N = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
INF = float('inf')
dp = [INF]*(H+1)
dp[0] = 0
for i in range(1,H+1):
  for k in AB:
    a = k[0]
    b = k[1]
    tmp = max(0,i-a)
    dp[i] = min(dp[i],dp[tmp]+b)
    
print(dp[H])
### BUGGY CODE ###

from collections import deque
N,M=[int(s) for s in input().split()] 
hito=[0 for i in range(N)]
edge=[set() for _ in range(N)]
for i in range(M):
  a,b=[int(s) for s in input().split()]
  edge[a-1].add(b-1)
  edge[b-1].add(a-1)


def dfs(start):
  count=1
  reach=deque([start])
  hito[start]=1
  while reach:
    _from=reach.pop()
    for _to in edge[_from]:
      if not(_to in reach) and hito[_to]==0:
        reach.append(_to)
        count+=1
        hito[_to]=1
  return(count)
 

ans=set()
for h in range(N):
  if hito[h]==0:
    ans.add(dfs(h))
print(max(ans))

### FIXED CODE ###

N,M=[int(s) for s in input().split()] 
hito=[0 for i in range(N)]
edge=[set() for _ in range(N)]
for i in range(M):
  a,b=[int(s) for s in input().split()]
  edge[a-1].add(b-1)
  edge[b-1].add(a-1)


def dfs(start):
  count=1
  reach=set()
  reach.add(start)
  hito[start]=1
  while reach:
    _from=reach.pop()
    for _to in edge[_from]:
      if not(_to in reach) and hito[_to]==0:
        reach.add(_to)
        count+=1
        hito[_to]=1
  return(count)
 

ans=set()
for h in range(N):
  if hito[h]==0:
    ans.add(dfs(h))
print(max(ans))
### BUGGY CODE ###

import itertools
n,k=map(int,input().split())
d=list(map(int,input().split()))
oll=list(itertools.product(['a','b','c','d'],repeat=k))
ans=0
for ol in oll:
    tv=0
    t=[]
    td=d[:]
    for o in ol:
        if o=='a':
            t+=[td.pop(0)]
            tv=sum(t)
            ans=max(ans,tv)
        elif o=='b':
            t+=[td.pop(-1)]
            tv=sum(t)
            ans=max(ans,tv)
        elif o=='c':
            if len(t)!=0:
                td.insert(0,min(t))
                t.remove(min(t))
                tv=sum(t)
                ans=max(ans,tv)
            else:
                break
        elif o=='d':
            if len(t)!=0:
                td.append(min(t))
                t.remove(min(t))
                tv=sum(t)
                ans=max(ans,tv)
            else:
                break
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
d=list(map(int,input().split()))
ans=0
for l in range(min(n,k)+1):
    for r in range(min(n-l,k-l)+1):
        tl=d[:l]+d[-r:] if r>0 else d[:l]
        tk=k-l-r
        s=0
        for t in sorted(tl):
            if t<0 and tk>0:
                s+=-t
                tk-=1
            ans=max(ans,sum(tl)+s)
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
if n==1:
        print(m)
else:
        max=1
        for i in range(1,m//n+1):
           if m%i==0:
                max=i
        print(max)

### FIXED CODE ###

import math

n,m=map(int,input().split())
if n==1:
        print(m)
else:
        l=[]
        for i in range(1,math.floor(m**0.5)+1):
           if m%i==0 and i<=m//n:
                l.append(i)
                if m//i<=m//n:
                        l.append(m//i)
        l.sort()
        print(l[-1])
### BUGGY CODE ###

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

for i in range(n):
    a_copy = copy.copy(a)
    del a_copy[i]
    c = collections.Counter(a_copy)
    cnt = 0
    for i in c.values():
        cnt += i * (i-1) // 2

    
    print(cnt)

### FIXED CODE ###

import collections
n = int(input())
a = list(map(int,input().split()))
cnt = 0
c = collections.Counter(a)
for i in c.values():
    cnt += i*(i-1) // 2
for j in range(n):
    print(cnt - c[a[j]] + 1)
### BUGGY CODE ###

# from collections import deque
import numpy as np
def main():
    n, m, k = map(int, input().split())
    A = np.array([0] + list(map(int, input().split())))
    B = np.array([0] + list(map(int, input().split())))
    X = np.cumsum(A)
    Y = np.cumsum(B)
    P = X[X <= k]
    Q = Y[Y <= k]
    n = len(P)
    m = len(Q)
    # print(P,Q)

    cnt = 0
    # Aをi個、Bをj個選ぶ
    for i in range(n)[::-1]:
        if i + m <= cnt:
            break
        else:
            for j in range(m)[::-1]:
                #print(i,j,X[i],Y[j])
                if X[i] + Y[j] <= k:
                    cnt = max(cnt, i + j)
                    break
    print(cnt)



if __name__ == "__main__":
    main()


### FIXED CODE ###

# from collections import deque
import numpy as np
def main():
    n, m, k = map(int, input().split())
    A = np.array([0] + list(map(int, input().split())))
    B = np.array([0] + list(map(int, input().split())))
    X = np.cumsum(A)
    Y = np.cumsum(B)
    # print(P,Q)

    cnt = 0
    j = m
    # Aをi個、Bをj個選ぶ
    for i, x in enumerate(X):
        if x > k:
            break

        while x + Y[j] > k:
            j -= 1
        cnt = max(cnt, i + j)

    print(cnt)

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

import heapq
N, M = list(map(int, input().split()))
tasks = []
for i in range(N):
    tasks.append(list(map(int, input().split())))

reward = []
heapq.heapify(reward)

total = 0
for i in range(M)[::-1]:
    for j in range(N):
        if tasks[j][0] == M - i:
            heapq.heappush(reward, -1 * tasks[j][1])
    if len(reward) > 0:
        total += heapq.heappop(reward) * (-1)

print(total)

### FIXED CODE ###

import heapq
N, M = list(map(int, input().split()))
days = [[] for _ in range(M + 1)]
for i in range(N):
    a, b = list(map(int, input().split()))
    if a > M: continue
    days[a].append(b)

reward = []
heapq.heapify(reward)

total = 0
for i in range(M)[::-1]:
    tasks = days[M - i]
    for task in tasks:
        heapq.heappush(reward, -1 * task)

    if len(reward) > 0:
        total += heapq.heappop(reward) * (-1)

print(total)
### BUGGY CODE ###

def main():
    import numpy as np
    mod = 10**9+7
    n, c = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    dp = np.zeros(c+1, dtype=np.int64)
    dp[0] = 1
    p = np.array([[pow(j, i, mod) for j in range(401)]
                  for i in range(401)], dtype=np.int64)
    for a, b in zip(A, B):
        q = np.sum(p[:, a:b+1], axis=1) % mod
        dp = np.array([sum(dp[i::-1]*q[:i+1] % mod)
                       for i in range(c+1)], dtype=np.int64) % mod
    print(dp[-1] % mod)


main()

### FIXED CODE ###

def main():
    mod = 10**9+7
    n, c = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    dp = [0]*(c+1)
    dp[0] = 1
    ans = 0

    p = [[0]*(401) for _ in [0]*401]  # p[i][j]でj^i
    for i in range(401):
        for j in range(401):
            p[i][j] = pow(j, i, mod)

    for a, b in zip(A, B):
        dp2 = [0]*(c+1)
        q = [0]*(c+1)
        for i in range(c+1):
            q[i] = sum(p[i][a:b+1]) % mod
        for i in range(c+1):
            temp = 0
            for j in range(i+1):
                temp += dp[i-j]*q[j]
            dp2[i] = temp % mod
        dp = dp2
    ans += dp[-1]
    print(ans % mod)


main()
### BUGGY CODE ###

# coding: utf-8
N, S = list(map(int, input().split()))
A = [0]+list(map(int, input().split()))

dt = [[0 for _ in range(S+1)] for x in range(N+1)]

for n in range(1, N+1):
  if A[n] <= S:
    dt[n][A[n]] += n
  for i in range(1,S+1):
    if (i + A[n]) <= S:
      dt[n][i+A[n]] += dt[n-1][i] - dt[n-2][i]
    dt[n][i] += dt[n-1][i] + (dt[n-1][i] - dt[n-2][i])

print(dt[N][S] % 998244353)

### FIXED CODE ###

# coding: utf-8
import numpy as np
N, S = list(map(int, input().split()))
A = [0]+list(map(int, input().split()))

dt = np.array([[0 for _ in range(S+1)] for x in range(N+1)])

for n in range(1, N+1):
  if A[n] <= S:
    dt[n,A[n]] += n
  if A[n] < S:
    dt[n, A[n]+1:] += dt[n-1,1:S-A[n]+1] - dt[n-2,1:S-A[n]+1]
  dt[n,:] += dt[n-1,:] * 2 - dt[n-2,:]
  dt[n,:] %= 998244353
print(dt[N,S] % 998244353)
### BUGGY CODE ###

n = int(input())
s = input()
def  bfs(i, j):
  cnt = 0
  bf = [s[i], s[j]]
  for k in range(j+1, n):
    if k-j == j-i:
      continue
    if s[k] not in bf:
      cnt += 1
if ('R' not in s) and ('G' not in s) and ('B' not in s):
  print(0)
else:
  cnt = 0
  for i in range(n-3):
    for j in range(i+1, n-1):
      si = s[i]
      sj = s[j]
      if si == sj:
          continue
      bf = [si,sj]
      for k in range(j+1, n):
        if k-j == j-i:
          continue
        if s[k] not in bf:
          cnt += 1
print(cnt)

### FIXED CODE ###

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

r = s.count('R')
g = s.count('G')
b = s.count('B')
cnt = 0
for j in range(n-2):
  sj = s[j]
  for i in range(1, (n-j)//2+1):
    if n <= j+2*i:
      break
    sd = s[j+i]
    sd2 = s[j+2*i]
    if (sj != sd) and (sj != sd2) and (sd != sd2):
      cnt += 1
print(r*g*b - cnt)
### BUGGY CODE ###

sosu  =[i+2 for i in range(99999)]
for i in range(len(sosu)):
    if sosu[i] != 0:
        i2 = (i+2)*2-2
        while i2 < len(sosu):
            sosu[i2] =0
            i2 += i+2
Q = int(input())
sosu.remove(0)
lis = []
for i in range(Q):
    lis.append(list(map(int,input().split())))
for i in lis:
    c,r = i
    count = 0
    while c <= r:
        if c in sosu:
            if int((c+1)/2) in sosu:
                count +=1
        c+=1
    print(count)


### FIXED CODE ###

# -*- coding: utf-8 -*-       
import math
def is_prime(x):
    if(x%2==0):return 0
    else:
        a = 3
        while(a<=math.sqrt(x)):
            if(x%a==0):return 0
            a += 2
    return 1
 
q = int(input())
MAX = 10**5+2
prime = [0 for i in range(MAX)]
alike = [0 for i in range(MAX)]
num = [0 for i in range(MAX)]
prime[2],prime[3] = 1,1
for i in range(4,MAX):
    prime[i] = is_prime(i)
for i in range(1,MAX-1,2):
    if(prime[i]==1 and prime[(i+1)//2]==1):
        alike[i] = 1
    num[i] = num[i-2]+alike[i]
    num[i+1] = num[i]
for i in range(q):
    l, r = list(map(int,input().split()))
    print(num[r]-num[l-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
https://beta.atcoder.jp/contests/abc082/tasks/arc087_b

"""
import sys
from sys import stdin
input = stdin.readline


def solve(s, gx, gy):
    n = len(s)
    forwards = [len(x) for x in s.split('T')]

    H = len(forwards)
    dpx = [False] * (n * 2 + 2)
    dpy = [False] * (n * 2 + 2)
    dpx[n + forwards[0]] = True
    dpy[n] = True

    for f in forwards[2::2]:
        if f == 0:
            continue
        t = [False] * (n * 2 + 2)
        for i in range(n*2 + 1):
            if dpx[i] is True:
                n_move = i - f
                p_move = i + f
                t[n_move] = True
                t[p_move] = True
        dpx = t

    for f in forwards[1::2]:
        if f == 0:
            continue
        t = [False] * (n * 2 + 2)
        for i in range(n * 2 + 1):
            if dpy[i] is True:
                n_move = i - f
                p_move = i + f
                t[n_move] = True
                t[p_move] = True
        dpy = t

    if dpy[gy + n] is True and dpx[gx + n] is True:
        return 'Yes'
    else:
        return 'No'


def main(args):
    s = input().strip()
    gx, gy = map(int, input().split())
    # s = 'FTFFTFFFT'
    # gx, gy = 4, 2

    ans = solve(s, gx, gy)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])
    


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
https://beta.atcoder.jp/contests/abc082/tasks/arc087_b

"""
import sys
from sys import stdin
input = stdin.readline


def check_x(forwards):
    n = sum(forwards[::2])      #  x軸方向への最大移動量
    dpx = [False] * (n * 2 + 1) #  真ん中を0として、±両方向のdp領域を確保
    dpx[forwards[0] + n] = True #  最初は0からプラス方向に移動

    for f in forwards[2::2]:
        if f == 0:
            continue
        n_move = dpx[f:] + [False]*f
        p_move = [False]*f + dpx[:-f]
        t = [a or b for a, b in zip(n_move, p_move)]
        dpx = t
    return dpx, n


def check_y(forwards):
    n = sum(forwards[1::2])
    dpy = [False] * (n * 2 + 1)
    dpy[n] = True

    for f in forwards[1::2]:
        if f == 0:
            continue
        n_move = dpy[f:] + [False]*f
        p_move = [False]*f + dpy[:-f]
        t = [a or b for a, b in zip(n_move, p_move)]
        dpy = t
    return dpy, n


def solve(s, gx, gy):
    forwards = [len(x) for x in s.split('T')] #  進む歩数情報の数字に変換
    dpx, zx = check_x(forwards)
    dpy, zy = check_y(forwards)

    if zx < abs(gx):
        return 'No'
    if zy < abs(gy):
        return 'No'
    if dpx[gx + zx] is True and dpy[gy + zy] is True:
        return 'Yes'
    else:
        return 'No'


def main(args):
    s = input().strip()
    gx, gy = map(int, input().split())
    # s = 'F'
    # gx, gy = -1, 0
    ans = solve(s, gx, gy)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])