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

## coding: UTF-8
N = int(input())
S = input()

#print(N)
#print(S)

def count_tern(s, leader): #文字列とリーダーのインデックスを引数にとる
    counter = 0
    for i in range(leader):
        if(s[i] == 'W'):
            counter += 1            
            #print("tern to E, i = {}, counter = {}".format(i,counter))
    #print("leader:{}".format(leader))
    for j in range(leader+1, len(s)):
        if(s[j] == 'E'):
            counter += 1
            #print("tern to W, j = {}, counter = {}".format(j, counter))
    return counter

answer = 1000
for i in range(len(S)):
    #print(count_tern(S, i))
    #print()
    if(count_tern(S, i) < answer):
        answer = count_tern(S, i)

print(answer)

### FIXED CODE ###

## coding: UTF-8
N = int(input())
S = input()
#s = []
#print(N)
#print(S)

#自分の手前までで左を向いている人の累積和リストをとりあえず作ってみる
sum_up_W = []
counter = 0
for i in range(N):
    sum_up_W.append(counter)
    if(S[i] == 'W'):
        counter += 1    
sum_up_W.append(counter) #最後にcounterを足さないと右端の人の影響が出ない。
#print(sum_up_W)
#右Eに振り向かせたいのはsum_up_W[i]
#リーダーより右で左を向いている人数はsum_up_W[N](全体で左を向いている人数)-sum_up_W[i+1](リーダーも含め、リーダーまでで左を向いている人数)
#左Wに振り向かせたいのは、リーダーより右で右を向いている人数： N-(i+1)（リーダーより右の全人数） - 上行の人数（リーダーより右で左を向いている人数）

ans = []
for i in range(N):
    ans.append(sum_up_W[i] + N - (i+1) - (sum_up_W[N] - sum_up_W[i+1])    )
print(min(ans))
'''
#これでもTLEします
#まず右（E）を向いている人を1、左（W）を向いている人を0に変換する
for i in range(len(S)):
    if(S[i] == 'E'):
        s.append(1)
    else:
        s.append(0)
#print(s)

#その地点までで左(W)を向いている人数を累積和するリストを作ります。要は右に振り向かせる人数リスト
E_count = []
#その地点から先で右(E)を向いている人数を累積和するリストを作ります。要は左に振り向かせる人数リスト
#W_count = []
#ans = []
for i in range(len(s)):
    E_count.append(  len(s[:i]) - sum(s[:i])  +   sum(s[i+1:]))
    #W_count.append(  sum(s[i+1:])  )
    #ans.append( E_count[i] + W_count[i])
#print(min(ans))
#print(E_count)
#print(W_count)
#for i in range(len(s)):
    #ans.append(E_count[i] + W_count[i])
print(min(E_count))
'''
'''
#これでもTLEします
def count_tern_new(s, leader):
    counter = 0
    #leaderより小さい人は右に向かせる。 左を向いている人数　＝　人数-右を向いている人数
    counter += len(s[:leader]) - sum(s[:leader])
    #leaderより大きい人には左を向かせる。 右を向いている人数
    counter += sum(s[leader+1:])
    return counter

answer_list_new = []
for i in range(len(s)):
    answer_list_new.append(count_tern_new(s, i))
print(min(answer_list_new))
'''


'''
#これだとTLEします。
def count_tern(s, leader): #文字列とリーダーのインデックスを引数にとる
    counter = 0
    for i in range(leader):
        if(s[i] == 'W'):
            counter += 1            
            #print("tern to E, i = {}, counter = {}".format(i,counter))
    #print("leader:{}".format(leader))
    for j in range(leader+1, len(s)):
        if(s[j] == 'E'):
            counter += 1
            #print("tern to W, j = {}, counter = {}".format(j, counter))
    return counter

#answer = 1000
answer_list = []
for i in range(len(S)):
    answer_list.append(count_tern(S, i))

#for i in range(len(S)):
    #print(count_tern(S, i))
    #print()
    #if(count_tern(S, i) < answer):
        #answer = count_tern(S, i)

print(min(answer_list))
'''
### BUGGY CODE ###

from collections import Counter
n = int(input())
s = []
for i in range(n):
    s.append(input())
cou = []

for i in range(n):
    cou.append(Counter(s[i]))

ans = 0
for i in range(n):
    for j in range(i+1,n):
        if cou[i]==cou[j]:
            ans += 1
print(ans)


### FIXED CODE ###

n = int(input())
d = {}
for _ in range(n):
    s = ''.join(sorted(input()))
    if s not in d:
        d[s] = 0
    d[s] += 1



ans = 0
for i in d.values():
    ans += int(i*(i-1)/2)
print(ans)
### BUGGY CODE ###

import collections

n, m = map(int, input().split())
dic = collections.defaultdict(lambda:[])
for _ in range(m):
  a, b = map(int, input().split())
  dic[a].append(b)
  dic[b].append(a)
  
ans = [None] * n
bfs = [(1,0)]
visited = set()
get = 0
while bfs and get < n:
  now, prev = bfs.pop(0)
  if now in visited:
    continue
  visited.add(now)
  get += 1
  if ans[now-1] == None:
    ans[now-1] = prev
  for next in dic[now]:
    if next not in visited:
      bfs.append((next, now))
      
print('Yes')  
for i in range(1, n):
  print(ans[i])

### FIXED CODE ###

import collections

n, m = map(int, input().split())
dic = collections.defaultdict(lambda:[])
for _ in range(m):
  a, b = map(int, input().split())
  dic[a].append(b)
  dic[b].append(a)
  
ans = [None] * n
bfs = [(1,dic[1])]
visited = set()
get = 0
while bfs and get < n:
  now, nexts = bfs.pop(0)

  for i in nexts:
    if i in visited:
      continue
    ans[i-1] = now
    get += 1
    bfs.append((i,dic[i]))
    visited.add(i)
      
print('Yes')  
for i in range(1, n):
  print(ans[i])
### BUGGY CODE ###

import sys
from scipy.sparse import coo_matrix
from scipy.sparse.csgraph import dijkstra

input = sys.stdin.readline
N = int(input())

P=set()
for _ in range(N - 1):
  a, b, c = map(int, input().split())
  P.add((c, a - 1, b - 1))

d, i, j = zip(*P)
G = coo_matrix((d, (i, j)),(N, N)).tocsc()

Q, K = map(int, input().split())
P = dijkstra(G, indices=K - 1, directed=False)
for _ in range(Q):
  x, y = map(int, input().split())
  print(int(P[x - 1] + P[y - 1]))

### FIXED CODE ###

from collections import deque

N = int(input())
ABC = [list(map(int, input().split())) for _ in range(N - 1)]
Q, K = map(int, input().split())
XY = [list(map(int, input().split())) for _ in range(Q)]

G = [[] * N for _ in range(N)]
for a, b, c in ABC:
  G[a - 1].append((b - 1, c))
  G[b - 1].append((a - 1, c))

D = [-1] * N
D[K - 1] = 0

q = deque()
q.append(K - 1)
while q:
  n = q.popleft()
  for i, c in G[n]:
    if D[i] < 0:
      q.append(i)
      D[i] = D[n] + c

for x, y in XY:
  print(D[x - 1] + D[y - 1])
### BUGGY CODE ###

import math

def comb_count(n, r):
    return math.factorial(n) // math.factorial(r) * math.factorial(n - r)

S = input()[::-1]
ans = 0

mods = [0] * 2019 #余りが0~2018
mods[0] = 1
current = 0

for i in range(len(S)):
    current = int(S[i]) * 10 ** i + current
    mod = current % 2019
    mods[mod] += 1

i = 0
for mod in mods:
    if mod > 1:
        ans += comb_count(mod, 2)
print(ans)



### FIXED CODE ###

import math

# def comb_count(n, r):
#     return math.factorial(n) // math.factorial(r) // math.factorial(n - r)

S = input()[::-1]
ans = 0

mods = [0] * 2019 #余りが0~2018
mods[0] = 1
current = 0
tmp = 1

for i in range(len(S)):
    current = (int(S[i]) * tmp + current) % 2019
    mod = current % 2019
    ans += mods[mod]
    mods[mod] += 1
    tmp = tmp * 10 % 2019

# for mod in mods:
#     if mod > 1:
#         ans += comb_count(mod, 2)
print(ans)
### BUGGY CODE ###

s = input()
a = []
for i in s:
  a.append(i)
  if len(a) >= 2 and a[-1] == "T" and a[-2] == "S":
    a = a[:-2]
print(len(a))

### FIXED CODE ###

s = input()
a = []
for i in s:
  a.append(i)
  if len(a) >= 2 and a[-1] == "T" and a[-2] == "S":
    a.pop()
    a.pop()
print(len(a))
### BUGGY CODE ###

import math
from collections import defaultdict

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

def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

pr = prime_factors(m)
di = {}
di = defaultdict(int)
for i in pr:
    while m % i == 0:
        m = m // i
        di[i] += 1
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

ans = 1
mod = 10 ** 9 + 7
for i in di:
    ans = ans * comb(di[i] + n - 1, di[i]) % mod
print(ans)

### FIXED CODE ###

import math
from collections import defaultdict

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

def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

pr = prime_factors(m)
di = {}
di = defaultdict(int)
for i in pr:
    while m % i == 0:
        m = m // i
        di[i] += 1

"""def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))"""
mod = 10 ** 9 + 7
MAX_N = 10 ** 5 + 100
factorial = [1] * MAX_N
def calc_factorial():
    for i in range(1, MAX_N):
        factorial[i] = i * factorial[i - 1] % mod

def comb(n, k):
    a = factorial[n] % mod
    b = (factorial[k] * factorial[n - k]) % mod
    b_ = pow(b, mod - 2, mod)
    return (a * b_) % mod


# 階乗を用意
calc_factorial()

ans = 1

for i in di:
    ans = ans * comb(di[i] + n - 1, di[i]) % mod
print(ans)
### BUGGY CODE ###

N,M=map(int,input().split())
mod=10**9+7
n1=-1
n2=-1
stop=0
A=[]
for i in range(M):
  n1=n2
  n2=int(input())
  if n2-n1==1:
    stop=1
  A.append(n2)
#print(A,stop,sep="おい")
if stop==1:
  print("0")
else:
  next=0
  dp=[0 for i in range(N+1)]
  dp[0]=1
  dp[-1]=0
  for i in range(1,N+1):
    if i in A:
      dp[i]=1
      next=1
    elif next==1:
      dp[i]=dp[i-2]
      next=2
    elif next==2:
      dp[i]=dp[i-1]
      next=0
    else:
      dp[i]=(dp[i-1]+dp[i-2])%mod
  print(dp[N]%mod)


### FIXED CODE ###

N,M=map(int,input().split())
mod=10**9+7
dp=[0]*(N+1)
dp[0]=1
dp[-1]=0
A=[]
for i in range(M):
  A.append(int(input()))
A=set(A)
#print(A)
for i in range(1,N+1):
  if dp[i-1]==0 and dp[i-2]==0:
    break
  elif i in A:
    continue
  else:
    dp[i]=(dp[i-1]+dp[i-2])%mod
print(dp[N]%mod)
### BUGGY CODE ###

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

N = int(input())
A = list(map(int,input().split()))
is_ball = [-1]*(N+1)
for i in range(N,-1,-1):
  is_ball[i] = A[i-1]
  divisors = make_divisors(i)
  if A[i-1] == 1:
    for div in divisors:
      A[div-1] ^= 1
      
b=[]

for i in range(1,N+1):
  if is_ball[i] == 1:
    b.append(i)
    
print(len(b))
print(" ".join(map(str,b)))
    
    


### FIXED CODE ###

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

N = int(input())
A = list(map(int,input().split()))
is_ball = [-1]*(N+1)
for i in range(N,-1,-1):
  is_ball[i] = A[i-1]
  divisors = make_divisors(i)
  if A[i-1] == 1:
    for div in divisors:
      A[div-1] ^= 1
      
b=[]

for i in range(1,N+1):
  if is_ball[i] == 1:
    b.append(i)
    
print(len(b))
print(" ".join(map(str,b)))
### BUGGY CODE ###

n=int(input())

d=[0]*(n+1)

for i in range(1,n+1):
    for j in range(i,n+1,i):
        d[j]+=1
        
ans=0
for j in range(n+1):
    ans+=j*d[j]
print(ans)

### FIXED CODE ###

n=int(input())

def sum_k(n):
    return n*(n+1)//2

ans=0
for i in range(1,n+1):
    ans+=i*sum_k(n//i)

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

# coding: utf-8
import numpy as np


def solve(*args: str) -> str:
    n = int(args[0])
    A = np.array(list(map(int, args[1].split())))

    ret = 0
    for i in range(1, n):
        ret += n-i-np.count_nonzero(A[i:]+A[:-i]-i)

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


### FIXED CODE ###

# coding: utf-8
from bisect import bisect_left
from collections import defaultdict


def solve(*args: str) -> str:
    n = int(args[0])
    A = list(map(int, args[1].split()))

    ret = 0
    X = defaultdict(list)
    for i, a in enumerate(A):
        X[a+i].append(i)

    for j, a in enumerate(A):
        if 0 <= j-a:
            ret += bisect_left(X[j-a], j)

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
### BUGGY CODE ###

p = 100
while 1:
	n = input()
	if n == 0: break
	xy = sorted([map(int,raw_input().split()) for i in range(n)])
	x,y = xy[0]
	xy = sorted(xy, key = lambda XY:(XY[0]-x)**2 + (XY[1]-y)**2)
	ans = 0
	for i in range(n-4):
		x1,y1 = xy[i]
		for j in range(n-3,i,-1):
			x2,y2 = xy[j]
			dx,dy = x2-x1,y2-y1
			if [x1-dy,y1-dx] in xy[j+1:j+p] and [x2+dy,y2-dx] in xy[j+1:j+p]:
				ans = dx**2+dy**2
			if [x1-dy,y1+dx] in xy[j+1:j+p] and [x2-dy,y2+dx] in xy[j+1:j+p]:
				ans = dx**2+dy**2
			if ans: break
		if ans: break
	print ans

### FIXED CODE ###

while 1:
	n = input()
	if n == 0: break
	xy = [map(int,raw_input().split()) for i in range(n)]
	S = set(map(tuple,xy))
	ans = 0
	for i in range(n-1):
		x1,y1 = xy[i]
		for j in range(i+1,n):
			x2,y2 = xy[j]
			a = (x2-y2+y1,y2+x2-x1)
			b = (x1-y2+y1,y1+x2-x1)
			if a in S and b in S:
				ans = max(ans,(x1-x2)**2 + (y1-y2)**2)
	print ans
### BUGGY CODE ###

n = int(input())
i=1
sum=0
num = []
for i in range(1,1000000000):
  while i>0:
    amari = i % 10
    if(amari != 3 or amari != 5 or amari != 7):
      break
    i = int(i / 10)    
  num.append(i)
j = 0
while num[j] <= n:
  sum += num[j]
  j += 1
print(sum)


### FIXED CODE ###

n = int(input())
def dfs(sss):
  if(int(sss) > n):
    return 0
  r = 1 if(all(sss.count(c) > 0 for c in '753')) else 0
  for c in '357':
    r += dfs(sss+c)
  return r
print(dfs('0'))
### BUGGY CODE ###

N = int(input())
dis = [0]*N
G = [[] for _ in range(N)]
for _ in range(N-1):
	u, v, w = map(int, input().split())
	u -= 1
	v -= 1
	G[u].append((v, w))
	G[v].append((u, w))

queue = [0]
V = [0]*N
idx = 1

while queue:
	u = queue.pop()
	for i in G[u]:
		v, w = i
		if v not in V:
			V[idx] = v
			idx += 1
			queue.append(v)
			dis[v] = dis[u] + w

for i in dis:
	print(1 if i % 2 else 0)

### FIXED CODE ###

N = int(input())
INF = float('inf')
dis = [INF]*N
dis[0] = 0
G = [[] for _ in range(N)]
for _ in range(N-1):
	u, v, w = map(int, input().split())
	u -= 1
	v -= 1
	G[u].append((v, w))
	G[v].append((u, w))

queue = [0]

while queue:
	u = queue.pop()
	for v, w in G[u]:
		if dis[v] > dis[u] + w:
			queue.append(v)
			dis[v] = dis[u] + w

for i in dis:
	print(i % 2)
### BUGGY CODE ###

A, B, N = map(int, input().split())
Ymax=0
if A*N < B:
  print(0)
elif N<B:
  Ymax = A*N // B
  print(Ymax)
else:
  for i in range(N,N-2*B,-1):
    if i<0:
      break
    x = i+1
    Y = int(A*x//B) - A*(x//B)
    if Y>Ymax:
      Ymax = Y
  print(Ymax)

### FIXED CODE ###

A, B, N = map(int, input().split())
Ymax=0
if A*N < B:
  print(0)
elif N<B:
  Ymax = A*N // B
  print(Ymax)
else:
  x = B-1
  Ymax = A*x//B - A*(x//B)
  print(Ymax)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
n, q = map(int, input().split())

ki = [[] for i in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    ki[a].append(b)
    ki[b].append(a)
# print(ki)

cnt = [0] * (n + 1)
for i in range(q):
    p, x = map(int, input().split())
    cnt[p] += x


# print(cnt)


def d(y, parent):
    for i in ki[y]:
        if i == parent:
            continue
        cnt[i] += cnt[y]
        d(i, y)


d(1, -1)
print(*cnt[1:])

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
n, q = map(int, input().split())

ki = [[] for i in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    ki[a].append(b)
    ki[b].append(a)
# print(ki)

cnt = [0] * (n + 1)
for i in range(q):
    p, x = map(int, input().split())
    cnt[p] += x


# print(cnt)


def d(y, parent):
    for i in ki[y]:
        if i == parent:
            continue
        cnt[i] += cnt[y]
        d(i, y)


d(1, -1)
print(*cnt[1:])
### BUGGY CODE ###

import bisect

N = int(input())
A = [int(input()) for _ in range(N)]

ans = 0
q = [A[0]]
p = A[0]
for i in range(1,N):
    if p >= A[i]:
        insert_index = bisect.bisect_left(q,A[i])
        if insert_index == 0:
            q = [A[i]] + q
            ans += 1
        else:
            q[insert_index-1] = A[i]
    else:
        insert_index = bisect.bisect_left(q,A[i])
        q[insert_index-1] = A[i]
    p = A[i]
print(len(q))


### FIXED CODE ###

from bisect import bisect_left
from collections import deque
import sys
input = sys.stdin.readline

N = int(input())
A = [int(input()) for _ in range(N)]

q = deque([A[0]])
for i in range(1,N):
    insert_index = bisect_left(q,A[i])
    if insert_index == 0:
        q.appendleft(A[i])
    else:
        q[insert_index-1] = A[i]

print(len(q))
### BUGGY CODE ###

n = input()
n = int(n)
s = []
for i in range(n):
	x = input()
	if x not in s: s.append(x)
print(len(s))


### FIXED CODE ###

n = input()
n = int(n)
s = set()
for i in range(n):
	x = input()
	s.add(x)
print(len(s))
### BUGGY CODE ###

N = int(input())
St = input()

#初期化
dp=[[0 for i in range(N+1)] for j in range(N+1)]

#DP:dp[i][j] Sのi文字目以降とj文字目以降の最大マッチング
for i in range(N-1,-1,-1):
  for j in range(N-1, i-1, -1):
    dp[i][j] = max(dp[i][j+1],dp[i+1][j])
    if St[i] == St[j]:
      dp[i][j] = min(max(dp[i][j], dp[i+1][j+1]+1),j-i)
      
ans = 0
for i in range(N+1):
  ans = max(ans, max(dp[i]))
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
from collections import deque

def is_ok(l):
    hs = set()
    q = deque()
    for i in range(N-l+1):
        h = S[i:i+l]
        if h in hs:
            return True
        q.append(h)
        if len(q) >= l:
            hs.add(q.popleft())
    return False

ok = 0
ng = N//2+1
while ng-ok > 1:
    m = (ng+ok)//2
    if is_ok(m):
        ok = m
    else:
        ng = m
print(ok)
### BUGGY CODE ###

n = int(input())
A = [int(input()) for _ in range(n)]
for j in range(n):
    print(max(A[0:j] + A[j+1:]))

### FIXED CODE ###

n = int(input())
A = [int(input()) for _ in range(n)]
max_id = A.index(max(A))
A = sorted(A, reverse=True)
for i in range(n):
    if i == max_id:
        # 最大値が取り除かれるので2番目に大きい数値を出力
        print(A[1])
    else:
        # 最大値が残っているので，最大値を出力
        print(A[0])
### BUGGY CODE ###

n = int(input())
a = map(int,input().split())
ans = 1

for i in a:
  ans *= i

if ans > 10 ** 18:
  ans = -1

print(ans)

### FIXED CODE ###

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

for i in range(n):
  ans *= a[i]
  if ans > 10 ** 18:
    ans = -1
    break

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

N, A = map(int,input().split())
X = list(map(int,input().split()))
dp = [[[0 for i in range(N*50+1)] for j in range(N+1)] for k in range(N+1)]
for i in range(N+1):
    dp[i][0][0] = 1
for i in range(1,N+1):
    x = X[i-1]
    for j in range(1,N+1):
        for k in range(N*50+1):
            if k < x:
                dp[i][j][k] = dp[i-1][j][k]
                
            elif j > i:
                dp[i][j][k] = 0
                
            else: 
                dp[i][j][k] += dp[i-1][j][k] + dp[i-1][j-1][k-x]
ans = 0
for i in range(1,N+1):
    ans += dp[N][i][A*i]
print(ans)

### FIXED CODE ###

N, A = map(int,input().split())
X = list(map(int,input().split()))
dp = [[[0 for i in range(N*50+1)] for j in range(N+1)] for k in range(N+1)]
for i in range(N+1):
    dp[i][0][0] = 1
for i in range(1,N+1):
    x = X[i-1]
    for j in range(1,N+1):
        for k in range(N*50+1):
            if k < x:
                dp[i][j][k] = dp[i-1][j][k]
                
            elif j > i:
                dp[i][j][k] = 0
                
            else: 
                dp[i][j][k] += dp[i-1][j][k] + dp[i-1][j-1][k-x]
ans = 0
for i in range(1,N+1):
    ans += dp[N][i][A*i]
print(ans)
### BUGGY CODE ###

N,T=map(int,input().split())
d=[None]*N
for i in range(N):
  a,b=map(int,input().split())
  d[i]=[a,b]

d=sorted(d,key=lambda x:x[0])
dp=[-1]*(3000*2+5)
dp[0]=0
for i in range(len(d)):
  for j in range(T-1,-1,-1):
    if dp[j]!=-1:
      if dp[j]+d[i][1]>dp[j+d[i][0]]:
        dp[j+d[i][0]]=dp[j]+d[i][1]
      
print(max(dp))

### FIXED CODE ###

N,T=map(int,input().split())
d=[None]*N
for i in range(N):
  a,b=map(int,input().split())
  d[i]=[a,b]

import numpy as np
d=sorted(d,key=lambda x:x[0])
dp=np.zeros(T,dtype=int)
ans=0
for i in range(len(d)):
  t=d[i][0]
  v=d[i][1]
  ans=max(ans,dp.max()+v)
  np.maximum(dp[:-t]+v,dp[t:],out=dp[t:])

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

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

MOD = 10 ** 9 + 7

fact = [1 for _ in range(N*M+1)]
for i in range(1, N*M+1):
    fact[i] = fact[i-1] * i

def inv(val):
    return pow(val, MOD-2, MOD)

def combination(n, m):
    return fact[n] * inv(fact[n-m]*fact[m]) % MOD

pattern = combination(N*M-2, K-2)

def diff_x_pattern(val):
    ret = 0
    for d in range(1, val):
        ret += ((val - d) * d) % MOD
    return ret

ans = (M * M * diff_x_pattern(N)) % MOD
ans += (N * N * diff_x_pattern(M)) % MOD
print((ans*pattern)%MOD)


### FIXED CODE ###

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

MOD = 10 ** 9 + 7

def combination(n, m):
    c = 1
    m = min(n-m, m)
    for i in range(m):
        c = c * (n-i) * pow(m-i, MOD-2, MOD) % MOD
    return c

pattern = combination(N*M-2, K-2)

def diff_x_pattern(val):
    ret = 0
    for d in range(1, val):
        ret += ((val - d) * d) % MOD
    return ret

ans = (M * M * diff_x_pattern(N)) % MOD
ans += (N * N * diff_x_pattern(M)) % MOD
print((ans*pattern)%MOD)
### BUGGY CODE ###

#B問題
R, G, B, N = map(int, input().split())

ans = 0
for r in range(0, N // R + 1):
    for g in range(0, 3001 - r):
        if (N - R*r - G*g) % B == 0 and (N - R*r - G*g)/B >=0:
            ans += 1
print(ans)            

### FIXED CODE ###

#B問題
import math
R, G, B, N = map(int, input().split())

ans = 0
if R == G == B == 1:
    print (int((N+2)*(N+1)/2))
else:
    for r in range(0, N // R + 1):
        for g in range(0, N // G + 1):
            if (N - R*r - G*g) % B == 0 and (N - R*r - G*g)/B >=0:
                ans += 1
    print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
def input():
    return sys.stdin.readline()[:-1]

def main():
    N, M = map(int, input().split())
    L = [0] * M
    R = [0] * M
    for i in range(M):
        L[i], R[i] = map(int, input().split())

    g = {}
    for i in range(1, N + 1):
        g[i] = 0

    for i in range(M):
        for j in range(L[i], R[i] + 1):
            g[j] += 1

    ans = 0
    for i in range(1, N + 1):
        if g[i] == M:
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
def input():
    return sys.stdin.readline()[:-1]

def main():
    N, M = map(int, input().split())
    L = [0] * M
    R = [0] * M
    for i in range(M):
        L[i], R[i] = map(int, input().split())

    ans = min(R) - max(L) + 1
    print(max(0, ans))

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

# 32:35
n = int(input())

heights = list(map(int, input().split()))

values = dict()

for ii, h in enumerate(heights):
    c1 = ii - h
    if (c1) in values:
        values[c1].append((ii, h))
    else:
        values[c1] = [(ii, h)]

count = dict()
for j, h in enumerate(heights):
    if (j + h) in values:
        for i, ai in values[j + h]:
            if i > 0 and i > j and not (j, i) in count:
                count[(j, i)] = True


print(len(count))

### FIXED CODE ###

# 32:35
n = int(input())

heights = list(map(int, input().split()))

values = dict()

for ii, h in enumerate(heights):
    c1 = ii - h
    if (c1) in values:
        values[c1].append((ii, h))
    else:
        values[c1] = [(ii, h)]

count = 0
for j, h in enumerate(heights):
    if (j + h) in values:
        count += len(values[j + h])
        # for i, ai in values[j + h]:
        #     if i > 0 and i > j and not (j, i) in count:
        #         count[(j, i)] = True


print(count)
### BUGGY CODE ###

# D - String Formation
s = input()
q = int(input())

fb = ['','']
odd = 0
for i in range(q):
    t,*fc = input().split()
    if t=='1': odd ^= 1 #t1
    else: #t2
        fb[odd ^ (int(fc[0])-1)] += fc[1]
        # if odd: #odd:reverse
        #     if fc[0]=='1': fb[1] += fc[1] #f1
        #     else: fb[0] += fc[1] #f2
        # else: #even
        #     if fc[0]=='1': fb[0] += fc[1] #f1
        #     else: fb[1] += fc[1] #f2

if odd: print(fb[1][::-1] + s[::-1] + fb[0])
else: print(fb[0][::-1] + s + fb[1])


### FIXED CODE ###

# D - String Formation
s = input()
q = int(input())
f = ''
b = ''
c = 0
for i in range(q):
    query = input().split()
    if query[0]=='1': c += 1 #t1
    else: #t2
        if c%2: #odd:reverse
            if query[1]=='1': #f1
                b += query[2]
            else: #f2
                f += query[2]
        else: #even
            if query[1]=='1': #f1
                f += query[2]
            else: #f2
                b += query[2]

if c%2: print(b[::-1] + s[::-1] + f) #odd
else: print(f[::-1] + s + b) #even