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

def answer():
    s = input()
    q = int(input())
    rev = False
    for i in range(q):
        query = input().split()

        if query[0] == '2':
            f, c = int(query[1]), query[2]
            if (not rev and f == 1) or (rev and f == 2):
                s = c + s
            else:
                s = s + c
        else:
            rev = not rev
    if rev:
        return s[::-1]
    return s

print(answer())

### FIXED CODE ###

from collections import deque

def answer():
    s = deque(input())
    q = int(input())
    rev = False
    for i in range(q):
        query = input().split()
        if int(query[0]) == 2:
            f, c = int(query[1]), query[2]
            if (not rev and f == 1) or (rev and f == 2):
                s.appendleft(c)
            else:
                s.append(c)
        else:
            rev = not rev
    if rev:
        s = list(s)
        s = s[::-1]
    print(''.join(s))
    return

answer()
### BUGGY CODE ###

from sys import stdin, setrecursionlimit as srl
from threading import stack_size, Thread
srl(int(1e9)+7)
stack_size(int(1e8))
 
def f(d):
    ans = 0
    if sum(d)==0:
        return 0
    try:
        return stored[(d[0],d[1],d[2])]
    except:
        pass
    ans += n/(d[0]+d[1]+d[2])
    x = d[0]/(d[0]+d[1]+d[2])
    ans += x*f([d[0]-1,d[1],d[2]])
    x = d[1]/(d[0]+d[1]+d[2])
    ans += x*f([d[0]+1,d[1]-1,d[2]])
    x = d[2]/(d[0]+d[1]+d[2])
    ans += x*f([d[0],d[1]+1,d[2]-1])
    stored[(d[0],d[1],d[2])] = ans
    return ans
 
 
n = int(input())
a = list(map(int,input().split()))
d = [0 for i in range(3)]
stored = {}
 
for i in a:
    d[i-1] +=1
 
print(f(d))

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
d = [0 for i in range(3)]
dp = [[[0 for i in range(n+1)] for j in range(n+1)] for k in range(n+1)] 
for i in a:
    d[i-1] +=1
for k in range(n+1):
    for j in range(n+1):
        for i in range(n+1):
            if i+j+k==0 or i+j+k>n:
                continue
            ans = n/(i+j+k)
            x = i/(i+j+k)
            if x:
                ans += x*dp[k][j][i-1]
            x = j/(i+j+k)
            if x:
                ans += x*dp[k][j-1][i+1]
            x = k/(i+j+k)
            if x:
                ans += x*dp[k-1][j+1][i]
            dp[k][j][i] = ans
print(dp[d[2]][d[1]][d[0]])
### BUGGY CODE ###

import itertools
N = int(input())
L = list(map(int, input().split()))
answer = 0

for i in itertools.combinations(L, 3):
    if i[0] >= i[1] + i[2]:
        continue
    elif i[1] >= i[0] + i[2]:
        continue
    elif i[2] >= i[1] + i[0]:
        continue
    else:
        answer += 1
print(answer)

### FIXED CODE ###

import itertools
import heapq
from bisect import bisect_left


def heapsort(iterable):
    h = []
    for value in iterable:
        heapq.heappush(h, value)
    return [heapq.heappop(h) for i in range(len(h))]

N = int(input())
L = list(map(int, input().split()))
L.sort()
# L_sort = heapsort(L)
# print (L)
answer = 0
for i, a in enumerate(L[0:N-2]):
    for j, b in enumerate(L[i+1:N-1]):
        index = bisect_left(L, a+b)
        answer += max(index - (j+i+1) -1, 0)
        # print(L, a+b, index, j+i+1, answer)
print(answer)
### BUGGY CODE ###

LARGE = 10 ** 9 + 7


def solve(n, a, b):

    pow_ab = [1] * (b + 1)
    for i in range(b):
        pow_ab[i + 1] = pow_ab[i] * (i + 1)
    pow_ab_inv = [1] * (b + 1)
    pow_ab_inv[-1] = pow(pow_ab[-1], LARGE - 2, LARGE)
    for i in range(b - 1, 0, -1):
        pow_ab_inv[i] = pow_ab_inv[i + 1] * (i + 1) % LARGE

    res_all = pow(2, n, LARGE) - 1
    res_ab = 1
    for i in range(a):
        res_ab *= (n - i)
    res_all -= res_ab * pow_ab_inv[a]
    for i in range(a, b):
        res_ab *= (n - i)
    res_all -= res_ab * pow_ab_inv[b]
    return res_all % LARGE


def main():
    n, a, b = map(int, input().split())
    res = solve(n, a, b)
    print(res)


def test():
    assert solve(4, 1, 3) == 7
    assert solve(1000000000, 141421, 173205) == 34076506


if __name__ == "__main__":
    test()
    main()


### FIXED CODE ###

LARGE = 10 ** 9 + 7


def solve(n, a, b):

    pow_ab = [1] * (b + 1)
    for i in range(b):
        pow_ab[i + 1] = pow_ab[i] * (i + 1) % LARGE
    pow_ab_inv = [1] * (b + 1)
    pow_ab_inv[-1] = pow(pow_ab[-1], LARGE - 2, LARGE)
    for i in range(b - 1, 0, -1):
        pow_ab_inv[i] = pow_ab_inv[i + 1] * (i + 1) % LARGE

    res_all = pow(2, n, LARGE) - 1
    res_ab = 1
    for i in range(a):
        res_ab *= (n - i)
        res_ab %= LARGE
    res_all -= res_ab * pow_ab_inv[a]
    for i in range(a, b):
        res_ab *= (n - i)
        res_ab %= LARGE
    res_all -= res_ab * pow_ab_inv[b]
    return res_all % LARGE


def main():
    n, a, b = map(int, input().split())
    res = solve(n, a, b)
    print(res)


def test():
    assert solve(4, 1, 3) == 7
    assert solve(1000000000, 141421, 173205) == 34076506


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

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

def solve(s,n):
    if "W" not in s or "R" not in s or s.find("WR")==-1:
        return 0

    else:
        arr=list(s)
        i=0
        j=n-1
        count=0
        brr=list(sorted(s))

        while arr!=brr:
            if arr[i]=="W" and arr[j]=="R":
                
                count += 1
                arr[i]="R"
                arr[j]="W"
                i+=1
                j-=1

            elif arr[i]=="W" and arr[j]=="W":
                j-=1
            elif arr[i]=="R" and arr[j]=="R":
                i+=1
            else:
                i+=1
                j-=1
        return count
print(solve(s,n))





### FIXED CODE ###

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

def solve(s,n):
    if "W" not in s or "R" not in s or s.find("WR")==-1:
        return 0

    else:
        arr=list(s)
        i=0
        j=n-1
        count=0

        while i<j:
            if arr[i]=="W" and arr[j]=="R":
                count += 1
                i+=1
                j-=1

            elif arr[i]=="W" and arr[j]=="W":
                j-=1
            elif arr[i]=="R" and arr[j]=="R":

                i+=1
            else:
                i+=1
                j-=1
        return count
print(solve(s,n))
### BUGGY CODE ###

#!/usr/bin/env python3
INF = float("inf")
import sys
input = sys.stdin.readline
from collections import*

def bfs():
    q = deque([(sx, sy)])
    dist = [[INF]*W for _ in range(H)]
    dist[sx][sy] = 0
    
    while q:
        x, y = q.popleft()
        if (x, y) == (gx, gy): return dist[gx][gy]
        for nx, ny in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:
            if 0<=nx<H and 0<=ny<W and dist[nx][ny] > dist[x][y]:
                if c[nx][ny] == ".":
                    dist[nx][ny] = dist[x][y]
                    q.appendleft((nx, ny))
        for nx in range(x-2, x+3):
            for ny in range(y-2, y+3):
                if 0<=nx<H and 0<=ny<W and dist[nx][ny] > dist[x][y]:
                    if c[nx][ny] == ".":
                        dist[nx][ny] = dist[x][y] + 1
                        q.append((nx, ny)) 
    return -1
H, W = map(int, input().split())

cx, cy = map(int, input().split()); sx, sy = cx - 1, cy - 1
dx, dy = map(int, input().split()); gx, gy = dx - 1, dy - 1
c = [input()[:-1] for _ in range(H)]
ans = bfs()
print(ans if ans != INF else -1)


### FIXED CODE ###

#!/usr/bin/env python3
INF = 10**7
import sys
input = sys.stdin.readline
from collections import*

def bfs():
    q = deque([(sx, sy)])
    dist = [[INF] * W for _ in range(H)]
    dist[sx][sy] = 0
    
    while q:
        x, y = q.popleft()
        b = dist[x][y]
        if (x, y) == (gx, gy):
            return b
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < H and 0 <= ny < W and dist[nx][ny] > b and c[nx][ny] == ".":
                dist[nx][ny] = b
                q.appendleft((nx, ny))
        B = b + 1
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                nx, ny = x + dx, y + dy
                if 0 <= nx < H and 0 <= ny < W and dist[nx][ny] > B and c[nx][ny] == ".":
                    dist[nx][ny] = B
                    q.append((nx, ny)) 
    return -1

H, W = map(int, input().split())
cx, cy = map(int, input().split())
dx, dy = map(int, input().split())
sx, sy, gx, gy = cx - 1, cy - 1, dx - 1, dy - 1
c = [input()[:-1] for _ in range(H)]
ans = bfs()
print(ans if ans != INF else -1)
### BUGGY CODE ###

def main():
    INF = float('inf')
    H,N = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    maxA = max(A for A,B in AB)
    dp = [INF]*(H+maxA)
    dp[0] = 0
    for i in range(H+maxA):
        if i <= 0:
            dp[i] = 0
        else:
            dp[i] = min(dp[i-A]+B for A,B in AB)
    print(min(dp[H:]))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    H,N = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    maxA = max(A for A,B in AB)
    dp = [0]*(H+maxA)
    for i in range(0,H+maxA):
        if i <= 0:
            dp[i] = 0
        else:
            dp[i] = min(dp[i-A]+B for A,B in AB)
    print(min(dp[H:]))


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

n,m=map(int,input().split())
list_p=[]
for i in range(0,m):
    a,b=map(int,input().split())
    list_p.append([a,b])
list_p.reverse()
group=[]
count=[]
group.append(list_p[0])
count.append(0)
for i in range(1,m):
    number=0
    for j in group:
        number=number+len(j)*(len(j)-1)//2
    count.append(number)
    index=0
    ifa=0
    ifb=0
    for j in group:
        if list_p[i][0] in j:
            ifa=1
            placea=index
        if list_p[i][1] in j:
            ifb=1
            placeb=index
        index=index+1
    if ifa==0 and ifb==0:
        group.append(list_p[i])
    elif ifa==1 and ifb==0:
        group[placea].append(list_p[i][1])
    elif ifa==0 and ifb==1:
        group[placeb].append(list_p[i][0])
    elif ifa==1 and ifb==1:
        if placea==placeb:
            pass
        else:
            group[placea].extend(group[placeb])
            group.pop(placeb)
x=n*(n-1)//2
count.reverse()
for i in count:
    print(x-i)


    


### FIXED CODE ###

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size=[1]*(n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y]=self.size[x]+self.size[y]
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.size[x]=self.size[x]+self.size[y]

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

    def Size(self,x):
        return self.size[self.find(x)]

n,m=map(int,input().split())
a_list=[]
b_list=[]
for i in range(m):
    a,b=map(int,input().split())
    a_list.append(a)
    b_list.append(b)
ans=[n*(n-1)//2]
U=UnionFind(n)
for i in range(m-1,0,-1):
    if U.same_check(a_list[i],b_list[i]):
        ans.append(ans[-1])
    else:
        ans.append(ans[-1]-U.Size(a_list[i])*U.Size(b_list[i]))
        U.union(a_list[i],b_list[i])
for i in range(m-1,-1,-1):
    print(ans[i])
### BUGGY CODE ###

import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    s = [int(i) for i in ipt().split()]
    s.sort(reverse=True)
    hq = [1]
    num = [0]*(2**(n+1)+1)
    num[0] = 10**10
    nqi = []
    for i in s:
#        print(hq)
        while hq:
            qi = hpq.heappop(hq)
            if num[qi//2] == i:
                if not hq:
                    print("No")
                    exit()
                nqi.append(qi)
                continue
            ndi = qi*(2**(n-len(str(format(qi,"b")))+1))
            while ndi > qi:
                num[ndi] = i
                hpq.heappush(hq,(ndi//2)*2+1)
                ndi //= 2
            num[qi] = i
            while nqi:
                hpq.heappush(hq,nqi.pop())
            break
    print("Yes")



if __name__ == '__main__':
    main()


### FIXED CODE ###

import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    s = [int(i) for i in ipt().split()]
    s.sort(reverse=True)
    al = [False]*(2**n)
    al[0] = True
    for i in range(n):
        usd = deque()
        cnt = 2**i
        for j,sj in enumerate(s):
            if al[j]:
                usd.append(sj)
            elif usd[0] > sj:
                usd.popleft()
                al[j] = True
                cnt -= 1
                if not cnt:
                    break
        if cnt != 0:
            print("No")
            exit()
    print("Yes")



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

N, K = list(map(int, input().split()))
H = list(map(int, input().split()))

if K <= len(H):
    for i in range(K):
        H.remove(max(H))
else:
    H = [0]
ans = sum(H)
print(ans)

### FIXED CODE ###

N, K = list(map(int, input().split()))
H = list(map(int, input().split()))

a = 0
b = 0
if N <= K:
    ans = 0
else:
    a = N - K

H.sort()
for i in range(a):
    b += H[i]
print(b)
### BUGGY CODE ###

H,W,K = map(int, input().split())
S = [list(map(int,(list(map(str,input().split()))[0]))) for i in range(H)]
#print(S)
import numpy as np
from itertools import product
"""
H,W,K = 3,5,2
S = [[1,1,1,0,0],
     [1,0,0,0,1],
     [0,0,1,1,1]]
"""

S = np.array(S,"uint8").T

if np.sum(S)<=K:
    print(0)
else:
    answer = H * W
    for X in product([False,True], repeat=H-1):#分けるか分けないか
        ans = np.sum(X)#横に切った回数
        #print(ans)
        M = [[0]]
        for i, x in enumerate(X):
            if x:
                M.append([])#切った回数箱を増やす
            M[-1].append(i+1)#後ろの箱に切る場所を入れていく
        #print(M)
        D = [0]*len(M)
        #print(D)
        for s in S:
            for k, m in enumerate(M):
                D[k] += np.sum(s[i] for i in m)
                #print("D",D)
            if any(d > K  for d in D):
                ans += 1
                #print("ans",ans)
                D[:] = [np.sum(s[i] for i in m) for m in M]
                
        if answer > ans:
            answer = ans

    print(min(answer,ans))

### FIXED CODE ###


def main():
    from itertools import product
    import numpy as np

    H,W,K = map(int, input().split())
    S = (np.array([list(map(int,list(input()))) for _ in range(H)]).T).tolist()

    if sum(sum(s) for s in S)<=K:
        print(0)
    else:
        answer = (H-1) * (W-1)
        for X in product([False,True], repeat=H-1):
            ans = np.sum(X)
            if ans >= answer:
                continue
            M = [[0]]
            for i, x in enumerate(X):
                if x:
                    M.append([])
                M[-1].append(i+1)
            D = [0]*len(M)
            for s in S:
                for k, m in enumerate(M):
                    D[k] += sum(s[i] for i in m)
                if any(d > K  for d in D):
                    ans += 1
                    if ans >= answer:
                        break
                    for k, m in enumerate(M):
                        D[k] = sum(s[i] for i in m)
                    
                    if any(d > K for d in D):
                        ans = answer + 1
                        break

            answer = min(answer,ans)

        print(answer)

main()
### BUGGY CODE ###

n,a=map(int,input().split())
x=list(map(int,input().split()))
l=max(max(x)*n+3,a*n+3)
dp=[[l*[0]for _ in range(n+1)]for _ in range(n+1)]
dp[0][0][0]=1
for i in range(1,n+1):
  for j in range(i+1):
    for k in range(l):dp[i][j][k]=dp[i-1][j][k]
  for j in range(1,i+1):
    for k in range(x[i-1],l):dp[i][j][k]+=dp[i-1][j-1][k-x[i-1]]
ans=0
for j in range(1,n+1):
  ans+=dp[-1][j][j*a]
print(ans)

### FIXED CODE ###

n,a=map(int,input().split())
x=list(map(int,input().split()))
X=max(max(x),a)
dp=[[[0]*(X*n+1)for j in range(n+1)]for i in range(n+1)]
dp[0][0][0]=1
for i in range(1,n+1):
  xi=x[i-1]
  for j in range(i+1):
      for h in range(j*X+1):
        if h<xi:dp[i][j][h]=dp[i-1][j][h]
        if xi<=h and j>=1:dp[i][j][h]=dp[i-1][j][h]+dp[i-1][j-1][h-xi]
ans=0
for j in range(1,n+1):ans+=dp[n][j][j*a]
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import random

D = int(input())
C = list(map(int,input().split()))
S = [list(map(int,input().split())) for i in range(D)]

sumC = sum(C)
def score(strategy):
    sat = 0
    last = [0]*26
    for i,ind in enumerate(strategy):
        last = [l+1 for l in last]
        last[ind] = 0
        sat -= sum((c*l for c,l in zip(C,last)))
        sat += S[i][ind]
    return sat

#first = [np.argmax(ds) for ds in S]
first = [i % 26 for i in range(D)]

ans = first
now_score = score(ans)

for i in range(5):
    for d in range(D):
        temp = ans[:]
        temp[d] = S[d].index(max(S[d]))
        new_score = score(temp)
        if new_score > now_score:
            now_score = new_score
            ans = temp

for i in range(10):
    samples = [random.randint(0,25) for j in range(D)]
    for d in range(D):
        temp = ans[:]
        temp[d] = samples[d]
        new_score = score(temp)
        if new_score > now_score:
            now_score = new_score
            ans = temp

for i in range(3):
    for d in range(D):
        temp = ans[:]
        temp[d] = S[d].index(max(S[d]))
        new_score = score(temp)
        if new_score > now_score:
            now_score = new_score
            ans = temp

for a in ans:
    print(a+1)



### FIXED CODE ###

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

D = int(input())
C = np.array(list(map(int,input().split())),dtype=np.int)
S = np.array([list(map(int,input().split())) for i in range(D)],dtype=np.int)

sumC = sum(C)
def score(strategy):
    sat = 0
    last = np.zeros(26).astype(np.int)
    for i,ind in enumerate(strategy):
        last += 1
        last[ind] = 0
        sat -= np.sum(C * last)
        sat += S[i][ind]
    return sat

#first = [np.argmax(ds) for ds in S]
first = [i % 26 for i in range(D)]

ans = first
now_score = score(ans)

for i in range(1):
    samples = np.random.randint(0,26,size=D).tolist()
    for d in range(D):
        temp = ans[:]
        temp[d] = samples[d]
        if score(temp) > now_score:
            ans = temp

for a in ans:
    print(a+1)
### BUGGY CODE ###

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

a = {}
for i in range(m):
    l,r = map(int,input().split())

    for j in range(l,r+1):
        if not j in a:
            a[j] = 1
        else:
            a[j] += 1

count = 0
for key in a.keys():
    if a[key] == m:  
        count +=1                

print(count)

### FIXED CODE ###

n,m = map(int,input().split())
 
min,max  = map(int,input().split())
for i in range(m-1):
    l,r = map(int,input().split())

    if l > max:
        print(0)
        exit(0)

    if r < min:
        print(0)
        exit(0)
 
    if l > min:
        min = l
    
    if r < max:
        max = r
  
 
print(max-min+1)
### BUGGY CODE ###

r,g,b,n = map(int, input().split())
ans = 0
for i in range(3001):
    for j in range(3001):
        a = (n - r*i - g*j)/b
        if a == int(a) and a >= 0:
            ans += 1
print(ans)

### FIXED CODE ###

r,g,b,n = map(int, input().split())
ans = 0
for i in range(3001):
    for j in range(3001):
        a = (n - r*i - g*j)/b
        if a == int(a) and a >= 0:
            ans += 1
print(ans)
### BUGGY CODE ###

N, Q = map(int, input().split(" "))
S = input()
for _ in range(Q):
    l, r = map(int, input().split(" "))
    s = S[l-1:r]
    print(int((len(s)-len("".join(s.split("AC"))))/2))

### FIXED CODE ###

N, Q = map(int, input().split(" "))
S = input()
t = [0] * (N+1)
for i in range(N):
    t[i+1] = t[i] + (1 if S[i:i+2] == "AC" else 0)
for i in range(Q):
    l, r = map(int, input().split(" "))
    print(t[r-1]-t[l-1])
### BUGGY CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
modulo = 998244353

s = sum(a)

dp = [[0] * (s + 1) for _ in range(n + 1)]
dp[0][0] = 1

cumsum = 0
for i in range(n):
    cumsum += a[i]
    for j in range(cumsum + 1):
        dp[i + 1][j] = dp[i][j] * 2
        if j - a[i] >= 0:
            dp[i + 1][j] += dp[i][j - a[i]]

        if dp[i + 1][j] > modulo:
            dp[i + 1][j] -= modulo
sol = 3 ** n - 3 * sum(dp[-1][int((s + 1) / 2) :])


if s % 2 == 0:
    dp = [[0] * (s + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    cumsum = 0
    for i in range(n):
        cumsum += a[i]
        for j in range(cumsum + 1):
            dp[i + 1][j] = dp[i][j]
            if j - a[i] >= 0:
                dp[i + 1][j] += dp[i][j - a[i]]

            if dp[i + 1][j] > modulo:
                dp[i + 1][j] -= modulo

    sol += 3 * dp[-1][s // 2]
sol %= modulo

print(sol)



### FIXED CODE ###

import numpy as np
from math import ceil

n = int(input())
a = [int(input()) for _ in range(n)]
modulo = 998244353

s = sum(a)

dp = np.zeros(s + 1, dtype=np.int)
dp[0] = 1
for ai in a:
    dp[ai:] = 2 * dp[ai:] + dp[:-ai]
    dp[:ai] = 2 * dp[:ai]
    dp %= modulo
sol = 3 ** n % modulo
sol -= 3 * dp[ceil(s / 2) :].sum()


if s % 2 == 0:
    dp = np.zeros(s + 1, dtype=np.int)
    dp[0] = 1
    for ai in a:
        dp[ai:] = dp[ai:] + dp[:-ai]
        dp %= modulo

    sol += 3 * dp[s // 2]

sol %= modulo

print(sol)
### BUGGY CODE ###

input()
s = input()

def f(i):
  return s[0:i].count('W') + s[i:].count('E')

arr = map(f, range(len(s)))

print(min(arr))

### FIXED CODE ###

input()
s = input()

l = 0
r = s[1:].count('E')
x = l + r

for i in range(1, len(s)):
  if s[i - 1] == 'W':
    l += 1

  if s[i] == 'E':
    r -= 1
  x = min(x, l + r)

print(x)
### BUGGY CODE ###

n = int(raw_input())
num_list = [int(raw_input()) for i in xrange(n)]
#print num_list

ans = 1 - pow(10, 9)

for i in range(n - 1):
  max_num = max(num_list[i+1:])
  tmp = max_num - num_list[i]
  if tmp > ans:
    ans = tmp

print ans

### FIXED CODE ###

n = int(raw_input())
num_list = [int(raw_input()) for i in xrange(n)]

minv = num_list[0]
maxv = -1000000000

for i in xrange(1, n):
  tmp = num_list[i] - minv
  maxv = tmp if tmp > maxv else maxv
  minv = num_list[i] if minv > num_list[i] else minv
  # print "i = %d, tmp = %d, maxv = %d, minv = %d" % (i, tmp, maxv, minv)

print maxv
### BUGGY CODE ###

n = int(input())
*a, = map(int, input().split())
q = int(input())
d = [0]*(10**5+1)
for i in a:
    d[i] += 1
for _ in [0]*q:
    b, c = map(int, input().split())
    d[c] += d[b]
    d[b] = 0
    print(sum(i*j for i, j in enumerate(d)))

### FIXED CODE ###

n = int(input())
*a, = map(int, input().split())
q = int(input())
d = {}
for i in a:
    if i in d:
        d[i] += 1
    else:
        d[i] = 1
ans = sum(a)
for _ in [0]*q:
    b, c = map(int, input().split())
    if b in d:
        if c in d:
            d[c] += d[b]
        else:
            d[c] = d[b]
        ans += (c-b)*d[b]
        d[b] = 0
    print(ans)
### BUGGY CODE ###

s = raw_input()
a = s.replace("ST","")
a2 = a.replace("ST", "")
while len(a) != len(a2):
	a = a2
	a2 = a2.replace("ST", "")
print len(a2)



### FIXED CODE ###

ipt = raw_input()
l = ""
for s in ipt:
    if not l:
        l += s
    elif l[-1]+s == "ST":
        l = l[:-1]
    else:
        l += s
print len(l)