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

def knapsack(N,W,w,v):
    dp = [[0]*(W+1) for _ in range(N)]
    
    for i in range(N):
        for j in range(W+1):
            if j-w[i]>=0:
                dp[i][j] = max(dp[i-1][j],v[i]+ dp[i-1][j-w[i]])
            else:
                dp[i][j] = dp[i-1][j]
    
    return dp[N-1][W]

N,W = map(int,input().split())
w = [0]*N
v = [0]*N
for i in range(N):
    w[i],v[i] = map(int,input().split())

print(knapsack(N,W,w,v))

### FIXED CODE ###

def knapsack(N,W,w,v):
    dp = [[0]*(W+1) for _ in range(N)]
    
    for i in range(N):
        for j in range(W+1):
            if j-w[i]>=0:
                dp[i][j] = max(dp[i-1][j],v[i]+ dp[i-1][j-w[i]])
            else:
                dp[i][j] = dp[i-1][j]
    
    return dp[N-1][W]

N,W = map(int,input().split())
w = [0]*N
v = [0]*N
for i in range(N):
    w[i],v[i] = map(int,input().split())

print(knapsack(N,W,w,v))
### BUGGY CODE ###

# import sys
# input = sys.stdin.readline

_, k = map(int, input().split())
s = list(map(int, list(input())))
# print(s)
is_count_zero = True
s0 = [0]
s1 = []
s0_ptr = 0
s1_ptr = -1
for c in s:
    if is_count_zero and c == 0:
        s0[s0_ptr] += 1
    elif not is_count_zero and c == 0:
        s0.append(1)
        s0_ptr += 1
        is_count_zero = True
    elif is_count_zero and c == 1:
        s1.append(1)
        s1_ptr += 1
        is_count_zero = False
    else: # not is_count_zero and c == 1
        s1[s1_ptr] += 1

# print(s0,s1)
# is_end_one = True if len(s0) == len(s1) else False

if k >= len(s0):
    print(sum(s0)+sum(s1))
elif k == 0:
    if s1 == []:
        print(0)
    else:
        print(max(s1))
else:
    ans = 0
    n = len(s0)-k+1
    for i in range(n):
        if i == 0 and s0[0] > 0:
            ans = sum(s0[:k]) + sum(s1[:k])
        elif i == n-1:
            ans = max(ans, sum(s0[i:]) + sum(s1[i-1:]))
        elif i != 0:
            ans = max(ans, sum(s0[i:i+k]) + sum(s1[i-1:i+k]) )
        # print(ans)
    print(ans)


### FIXED CODE ###

# import sys
# input = sys.stdin.readline

_, k = map(int, input().split())
s = list(map(int, list(input())))
# print(s)
is_count_zero = True
s0 = [0]
s1 = []
s0_ptr = 0
s1_ptr = -1
for c in s:
    if is_count_zero and c == 0:
        s0[s0_ptr] += 1
    elif not is_count_zero and c == 0:
        s0.append(1)
        s0_ptr += 1
        is_count_zero = True
    elif is_count_zero and c == 1:
        s1.append(1)
        s1_ptr += 1
        is_count_zero = False
    else: # not is_count_zero and c == 1
        s1[s1_ptr] += 1

# print(s0,s1)
is_end_one = True if len(s0) == len(s1) else False

if k >= len(s0):
    print(sum(s0)+sum(s1))
# elif k == 0:
#     if s1 == []:
#         print(0)
#     else:
#         print(max(s1))
else:
    ans = 0
    sum_range = 0
    n = len(s0)-k+1
    for i in range(n):
        if i == 0:
            sum_range = sum(s0[:k]) + sum(s1[:k])
            ans = max(ans, sum_range)
        elif i == n-1:
            sum_range = sum(s0[i:]) + sum(s1[i-1:])
            ans = max(ans, sum_range)
        elif i == 1:
            sum_range = sum_range - s0[0] + s0[k] + s1[k]
            ans = max(ans, sum_range)
        elif i != 0:
            sum_range = sum_range - s0[i-1] + s0[i+k-1] - s1[i-2] + s1[i+k-1]
            ans = max(ans, sum_range)
    print(ans)
### BUGGY CODE ###

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

H,W = map(int, input().split())
Ch,Cw = map(int, input().split())
Dh,Dw = map(int, input().split())
S = [input() for _ in range(H)]

A = [[-1 for _ in range(W)] for _ in range(H)]
A[Ch-1][Cw-1] = 0

def isValid(h,w):
  return h>=0 and h<H and w>=0 and w<W and S[h][w]=='.' and A[h][w]==-1

warp = 0
BFS_now = set()
BFS_now.add((Ch-1, Cw-1))
BFS_search = set()
BFS_search.add((Ch-1, Cw-1))
ij = [(-1,0),(0,-1),(0,1),(1,0)]

while len(BFS_now)>0:
  while len(BFS_search)>0:
    BFS_search_tmp = set()
    for h,w in BFS_search:
      for i,j in ij:
        if isValid(h+i,w+j):
          BFS_search_tmp.add((h+i,w+j))
          BFS_now.add((h+i,w+j))
          A[h+i][w+j] = warp
    BFS_search = BFS_search_tmp.copy()
  BFS_now_tmp = set()
  for h,w in BFS_now:
    for i in range(-2,3):
      for j in range(-2,3):
        if isValid(h+i,w+j):
          BFS_now_tmp.add((h+i,w+j))
          A[h+i][w+j] = warp + 1
  BFS_now = BFS_now_tmp.copy()
  BFS_search = BFS_now_tmp.copy()
  warp += 1

print(A[Dh-1][Dw-1])

### FIXED CODE ###

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

H,W = map(int, input().split())
Ch,Cw = map(int, input().split())
Dh,Dw = map(int, input().split())
S = [input() for _ in range(H)]

A = [[-1 for _ in range(W)] for _ in range(H)]
A[Ch-1][Cw-1] = 0

def isValid(h,w):
  if h>=0 and h<H and w>=0 and w<W and S[h][w]=='.' and A[h][w]==-1:
    return True
  else:
    return False

warp = 0
BFS_now = [(Ch-1, Cw-1)]
BFS_search = [(Ch-1, Cw-1)]
ij = [(-1,0),(0,-1),(0,1),(1,0)]
while len(BFS_now)>0:
  while len(BFS_search)>0:
    BFS_search_tmp = []
    for h,w in BFS_search:
      for i,j in ij:
        if isValid(h+i,w+j):
          BFS_search_tmp.append((h+i,w+j))
          A[h+i][w+j] = warp
    BFS_now += BFS_search_tmp
    BFS_search = BFS_search_tmp
  BFS_now_tmp = []
  for h,w in BFS_now:
    for i in range(-2,3):
      for j in range(-2,3):
        if isValid(h+i,w+j):
          BFS_now_tmp.append((h+i,w+j))
          A[h+i][w+j] = warp + 1
  BFS_now = BFS_now_tmp
  BFS_search = BFS_now_tmp
  warp += 1

print(A[Dh-1][Dw-1])
### BUGGY CODE ###

N = int(input())
S = []
for x in range(N):
    S.append(input())
P = sorted(set(S))
maxi = max([S.count(x) for x in P])
done = []
for x in P:
    if S.count(x) == maxi:
        print(x)

### FIXED CODE ###

from collections import defaultdict

N = int(input())
ans = dict()
for _ in range(N):
    k = str(input())
    if k in ans:
        ans[k] += 1
    else:
        ans.update({k: 1})
groupedByValue = defaultdict(list)
for key, value in sorted(ans.items()):
    groupedByValue[value].append(key)
l = groupedByValue[max(groupedByValue)]
for i in l:
    print(i)
### BUGGY CODE ###

import sys
readline = sys.stdin.readline

def main():
    s = input()
    q = int(input())

    hanten = 0 # 偶数なら正常、 奇数なら反転状態

    front = "" # リストの前に追加するのは、O(n)なので避ける
    back = ""

    for _ in range(q):
        tmp = readline().split()
        if len(tmp) == 1:
            hanten ^= 1
        else:
            if hanten: # 反対ver
                if tmp[1] == '1':
                    back += tmp[2]
                else:
                    front += tmp[2]
            else: # 正常
                if tmp[1] == '1':
                    front += tmp[2]
                else:
                    back += tmp[2]

    if hanten == 0:
        print(front[::-1] + s + back)
    else:
        print((front[::-1] + s + back)[::-1])

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
readline = sys.stdin.readline

def main():
    s = input()
    q = int(input())

    hanten = 0 # 偶数なら正常、 奇数なら反転状態

    front = "" # リストの前に追加するのは、O(n)なので避ける
    back = ""

    for _ in range(q):
        tmp = readline().split()
        if len(tmp) == 1:
            hanten ^= 1
        else:
            if hanten: # 反対ver
                if tmp[1] == '1':
                    back += tmp[2]
                else:
                    front += tmp[2]
            else: # 正常
                if tmp[1] == '1':
                    front += tmp[2]
                else:
                    back += tmp[2]

    if hanten == 0:
        print(front[::-1] + s + back)
    else:
        print((front[::-1] + s + back)[::-1])

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

import math
from collections import Counter
def ip():return int(input())
def imp():return map(int,input().split())
def impstr():return map(str,input().split())
def limp():return list(map(int,input().split()))
def limpstr():return list(map(str,input().split()))
def prime(x):
    for i in range(2,int(math.sqrt(x))+1):
        if x%i==0:return False
    return True

n=ip()
l=limp()
if 1 in l:
    if l.count(1)==1:print(1)
    else:print(0)
    exit()
else:
    #l.sort()
    c=Counter(l)
    ans=0
    for k,v in c.items():
        if v>1:continue
        elif prime(k)==True:ans+=1
        else:
            f=True
            ys=[]
            for i in range(2, int(math.sqrt(k)) + 1):
                if k % i == 0 and (i in c or k//i in c):
                    f=False
                    break
            if f==True:ans+=1

    print(ans)



### FIXED CODE ###

import math
from collections import Counter
def ip():return int(input())
def imp():return map(int,input().split())
def impstr():return map(str,input().split())
def limp():return list(map(int,input().split()))
def limpstr():return list(map(str,input().split()))

n=ip()
l=limp()
if 1 in l:
    if l.count(1)==1:print(1)
    else:print(0)
    exit()
else:
    mark=[0]*(10**6+5)
    for x in l:
        if mark[x]>=1:   #X已经出现了一次
            mark[x]=2
            continue
        mark[x]=1
        i=2
        while x*i<10**6+1:
            mark[x*i]=2
            i+=1
    ans=0
    for x in l:
        if mark[x]==1:ans+=1
    print(ans)
### BUGGY CODE ###

import sys
INF=100000000
cost_value=1000000000000
def frog(i,K,h,dp):
    global INF,cost_value
    if dp[i]!=INF:
        return dp[i]
    else:
        cost=cost_value
        for k in range(1,K+1):
            if i-k-1>=0:
                x=frog(i-k,K,h,dp)+abs(h[i-1]-h[i-k-1])
                if cost>x:
                    cost=x
                continue
            
        dp[i]=cost
        return dp[i]
sys.setrecursionlimit(INF)
N,K=map(int,input().split())
h=list(map(int,input().split()))
dp=[INF for i in range(N+1)]
dp[1]=0
dp[2]=abs(h[1]-h[0])
print(frog(N,K,h,dp))


### FIXED CODE ###

import numpy as np
N,K=map(int,input().split())
h=list(map(int,input().split()))
h=np.array(h)
cost=np.zeros(N+1)
cost[1]=0
cost[2]=abs(h[1]-h[0])
for i in range(3,N+1):
    x=1 if i-K<=1 else i-K
    cost[i]=(cost[x:i]+abs(h[i-1]-h[x-1:i-1])).min()
print(int(cost[N]))
### BUGGY CODE ###

### 解答
N, K = map(int, input().split())
A = list(map(int, input().split()))

#B = [0]*N                                 # 記録用のリスト

for k in range(K):                        # 以降の操作をK回繰り返す
  B = [0]*N 
  for i in range(N):                      # 各電球によって照らされる範囲を考える
    start = max(0, i-A[i])                # 始点のインデックスは0かi-A[i]
    end = min(N, i+A[i]+1)                # 終点のインデックスはNかi+A[i]+1
    B[start] += 1                         # 始点に+1を記録する
    if end <= N - 1:
      B[end] -= 1                         # 終点に電球が存在する場合は-1を記録する
  bsum = B[0]
  for i in range(1, N):                   # 累積和の計算
    B[i] = B[i-1] + B[i]
    bsum += B[i]

  
  A = B                                   # AをBで更新してつぎのループへ
  
  if bsum == N**2:                        # すべての電球がN個の電球に照らされるタイミングでbreakする
    break

print(*A)                                 # リストAの中身を順に表示

### FIXED CODE ###

import numpy as np
from numba import njit
 
n, k = map(int, input().split())
a = np.array(list(map(int, input().split())), dtype=np.int64)
 
@njit
def loop1(a):
  b = np.zeros(n+1, dtype=np.int64)
  for i in range(n):
    l = max(0, i-a[i])
    r = min(i+a[i]+1, n)
    b[l] += 1
    if r <= n-1: b[r] -= 1
  
  b = np.cumsum(b)[:-1]
  return b
 
for q in range(min(42, k)):
  a = loop1(a)
    
print(*a)
### BUGGY CODE ###

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

ans = 1

for x in range(n):
    if 0 in a:
        ans = 0
        break

    ans *= a[x]

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


print(ans)


### FIXED CODE ###

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

ans = 1

a.sort(reverse=True)

if 0 not in a:
    for x in range(n):
        ans *= a[x]

        if ans > 10**18:
            ans = -1
            break
else:
    ans = 0

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

# -*- coding: utf-8 -*-
import sys


def get_num():
    return int(input())


def get_nums(n):
    res = [0 for _ in range(n)]
    for i in range(n):
        res[i] = int(input())
    return res


def get_numbers():
    return map(int, input().split())

n, k = get_numbers()
s = [int(c) for c in input()]

rle = list()
target = 1
cnt = 0
for i in range(n):
    if s[i] == target:
        cnt += 1
    else:
        target = 1 - target
        rle.append(cnt)
        cnt = 1
rle.append(cnt)
if target == 0:
    rle.append(0)

length = len(rle)
ans = 0
for l in range(0, length, 2):
    r = min(l + 2 * k + 1, length)
    ans = max(sum(rle[l:r]), ans)

print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
n, k = map(int, input().split())
s = list(map(int, input()))

# Run Length Encoding
rle = list()
target = 1
count = 0
for i in range(n):
    if s[i] == target:
        count += 1
    else:
        target = 1 - target
        rle.append(count)
        count = 1
rle.append(count)
if target == 0:
    rle.append(0)

offset = 2 * k + 1
res = 0

# two pointers
left = 0
right = 0
cand = 0
for i in range(0, len(rle), 2):
    next_left = i
    next_right = min(i + offset, len(rle))

    while(next_left > left):
        cand -= rle[left]
        left += 1

    while(next_right > right):
        cand += rle[right]
        right += 1

    res = max(res, cand)

print(res)
### BUGGY CODE ###

def binary_search(S, key):
    mid = len(S) // 2

    if len(S) == 0:
        return 0
    
    if S[mid] == key:
        return 1

    if S[mid] >= key:
        if binary_search(S[:mid], key):
            return 1
    else:
        if binary_search(S[mid + 1:], key):
            return 1

    return 0

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

q = int(input())
T = [int(i) for i in input().split(' ')]

result = 0
for t in T:
    result += binary_search(S, t)

print(result)


### FIXED CODE ###

def binary_search(S, key):
    S_len = len(S)

    if S_len == 0:
        return -1

    mid = S_len // 2

    if S[mid] == key:
        return 1

    if S[mid] >= key:
        return binary_search(S[:mid], key)
    else:
        return binary_search(S[mid + 1:], key)

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

q = int(input())
T = [int(i) for i in input().split(' ')]

result = 0

for t in T:
    left, right = 0, n
    while left < right:
        mid = (right + left) // 2
        if S[mid] == t:
            result += 1
            break

        if S[mid] > t:
            right = mid
        else:
            left = mid + 1

print(result)
### BUGGY CODE ###


N=input()
N=int(N)
A=10**12
I=((N**(1/2))//1)

for a in range(1,round(I+1)):
    for b in range(a,(10**12)+1):
        if N==a*b:
            if a+b-2<A:
                A=a+b-2
            else:
                pass
        else:
            pass

print(A)

### FIXED CODE ###

N=int(input())
ans=1000000000000
import math

for i in range(int(math.sqrt(N))):
    j=N/(i+1)
    if j%1==0:
        if i+int(j)-1<ans:
            ans=i+int(j)-1

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

#D in [S_i-X_i,T_i-X_i) → Xiで止まる
import sys
input = sys.stdin.readline
from heapq import heappop,heappush
from collections import defaultdict

N,Q = map(int,input().split())
task = []

STX = [[int(x) for x in input().split()] for _ in range(N)]
for s,t,x in STX:
  task.append((t-x,0,x)) # xで止まらなくなる
  task.append((s-x,1,x)) # xで止まる

for i in range(Q):
  d = int(input())
  task.append((d,2,i)) # 止まる位置を答える
answer = [-1]*Q

task.sort()

# 引っかかってる場所の管理
se = set()
se_hp = [] # heapで最小値を先頭に保つ

# 小さい時刻から順に見ていく
for a,b,c in task:
  if not b: # b == 0
    se.remove(c)
  elif b&1: # b == 1
    se.add(c)
    heappush(se_hp,c)
  else: # b == 2
    while se_hp and se_hp[0] not in se:
      heappop(se_hp)
    answer[c] = se_hp[0] if se_hp else -1

print('\n'.join(map(str,answer)))


### FIXED CODE ###

#D in [S_i-X_i,T_i-X_i) → Xiで止まる
import sys
input = sys.stdin.readline

N,Q = map(int,input().split())
q = []

STX = [[int(x) for x in input().split()] for _ in range(N)]
for s,t,x in STX:
  q.append((s-x,1,x)) # xで死ぬ
  q.append((t-x,0,x)) # xで死ななくなる

for i in range(Q):
  d = int(input())
  q.append((d,2,i))
answer = [-1]*Q

se = set() # 引っかかってる場所

q.sort()

min_se = 10**18
flag = False # min_seが正しい

for a,c,b in q:
  if not c:
    se.remove(b)
    if min_se == b:
      flag = False
  elif c&1:
    se.add(b)
    if b < min_se:
      min_se = b
      flag = True
  else:
    if se:
      if not flag:
        min_se = min(se)
        flag = True
      answer[b] = min_se

print('\n'.join(map(str,answer)))
### BUGGY CODE ###

import sys


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


MOD = 998244353
n = int(input())
xys = []
ys = []
for line in sys.stdin:
    x, y = map(int, line.split())
    xys.append((x, y))
    ys.append(y)
ys.sort()
y_dict = {y: i + 1 for i, y in enumerate(ys)}
xys = [(x, y_dict[y]) for x, y in xys]
xys.sort()
bit = Bit(n)

p2d = [1]
for i in range(n):
    p2d.append(p2d[-1] * 2 % MOD)

ans = 0
for i, (x, y) in enumerate(xys):
    a = bit.sum(y)
    b = i - a
    c = y - a - 1
    d = (n - i - 1) - c
    bit.add(y, 1)
    # print(i, x, y, a, b, c, d)
    pa, pb, pc, pd = p2d[a], p2d[b], p2d[c], p2d[d]
    tmp = p2d[n - 1]
    tmp += (pa - 1) * (pd - 1) * (pb + pc - 1) % MOD
    tmp += (pb - 1) * (pc - 1) % MOD * pa * pd % MOD
    ans = (ans + tmp) % MOD
print(ans)


### FIXED CODE ###

import sys


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


MOD = 998244353
n = int(input())
xys = []
ys = []
for line in sys.stdin:
    x, y = map(int, line.split())
    xys.append((x, y))
    ys.append(y)
ys.sort()
y_dict = {y: i + 1 for i, y in enumerate(ys)}
xys = [(x, y_dict[y]) for x, y in xys]
xys.sort()
f_bit = Bit(n)
b_bit = Bit(n)
for i in range(1, n + 1):
    b_bit.add(i, 1)

p2d = [1]
for i in range(n):
    p2d.append(p2d[-1] * 2 % MOD)

ans = 0
for i, (x, y) in enumerate(xys):
    b_bit.add(y, -1)
    a = f_bit.sum(y)
    b = i - a
    c = b_bit.sum(y)
    d = (n - i - 1) - c
    f_bit.add(y, 1)
    # print(i, x, y, a, b, c, d)
    pa, pb, pc, pd = p2d[a], p2d[b], p2d[c], p2d[d]
    tmp = p2d[n - 1]
    tmp += (pa - 1) * (pd - 1) * pb * pc
    tmp += (pb - 1) * (pc - 1) * pa * pd
    tmp -= (pa - 1) * (pb - 1) * (pc - 1) * (pd - 1)
    ans = (ans + tmp) % MOD
print(ans)
### BUGGY CODE ###

n,k = map(int,input().split())         # n=町の個数 , k=テレポート回数
a_list = list(map(int,input().split()))         # 各町のテレポート先リスト
dum = a_list[0]                        # dum=次のテレポート先
k = k - 1                              # テレポート回数をデクリメント
ans_list = [1]                         # 訪れた町を ans_list に格納
ok = True
while(1):
    #print(dum,ans_list)
    if ans_list.count(dum) == 1:
        ind = ans_list.index(dum)
        loop = ans_list[ind:]
        len_loop = len(loop)
        k = k % len_loop
        ans_list = []
        ok = False

    if k == 0:
        print(int(dum))
        break
    if ok:
        ans_list.append(dum)
    dum = a_list[int(dum)-1]
    k = k - 1



### FIXED CODE ###

n,k = map(int,input().split())         # n=町の個数 , k=テレポート回数
a_list = list(map(int,input().split()))     # 各町のテレポート先リスト
dum = a_list[0]                        # dum=次のテレポート先
k = k - 1                              # テレポート回数をデクリメント
ans_list = [1]                         # 訪れた町を ans_list に格納
ok = True
check_list = n*[0]
check_list[0] = 1
for i in range(k+1):
    if ok and check_list[dum-1] == 1:
        #print(dum,111)
        ind = ans_list.index(dum)
        loop = ans_list[ind:]
        len_loop = len(loop)
        k = k % len_loop
        ans_list = []
        ok = False
    else:
        check_list[dum-1] = 1

    if k == 0:
        print(int(dum))
        break
    ans_list.append(dum)
    dum = a_list[int(dum)-1]
    k = k - 1
### BUGGY CODE ###

N = int(input().rstrip())
line = input().rstrip()
l = [int(v) for v in line.split()]
l.sort()
uniq_list = sorted(list(set(l)))
result = 0
for i in range(len(uniq_list)):
    j = l.index(uniq_list[i])
    if (N / 2) == j:
        result = uniq_list[i] - uniq_list[i - 1]
        break

print(result)


### FIXED CODE ###

N = int(input().rstrip())
line = input().rstrip()
l = [int(v) for v in line.split()]
l.sort()
uniq_list = sorted(list(set(l)))
result = 0
start_at = 0
for i in range(len(uniq_list)):
    for j in range(start_at, len(l)):
        if uniq_list[i] == l[j]:
            if (N / 2) == j:
                result = uniq_list[i] - uniq_list[i - 1]
            else:
                start_at = j + 1
            
            break

print(result)
### BUGGY CODE ###

reverseFlag = False

S = input()
Q = int(input())

for i in range(Q):
    TFC = input().split(' ')
    if TFC[0] == '1':
        S = S[::-1]
    else:
        if TFC[1] == '1':
            S = TFC[2] + S
        else:
            S = S + TFC[2]
print(S)

### FIXED CODE ###

reverseFlag = False

S = input()
Q = int(input())
S_mae = ''
S_ato = ''

for i in range(Q):
    TFC = input().split(' ')
    if TFC[0] == '1':
        reverseFlag = not reverseFlag
    else:
        if TFC[1] == '1':
            if reverseFlag:
                S_ato = S_ato + TFC[2]
            else:
                S_mae = TFC[2] + S_mae
        else:
            if reverseFlag:
                S_mae = TFC[2] + S_mae
            else:
                S_ato = S_ato + TFC[2]
if reverseFlag:
    print(S_ato[::-1] + S[::-1] + S_mae[::-1])
else:
    print(S_mae + S + S_ato)
### BUGGY CODE ###

N = int(input())
L = list(map(int, input().split()))
L.sort()
from itertools import combinations

ans = 0
for a, b, c in combinations(L, r=3):
    ans += a + b > c
print(ans)


### FIXED CODE ###

# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


N = read_a_int()
L = read_ints()
L.sort()
# import numpy as np
# L = np.array(L)
from bisect import bisect_left

cnt = 0
for i in range(N):
    a = L[i]
    for j in range(i+1, N):
        b = L[j]
        # ここで二分探索するか
        cnt += bisect_left(L, a+b) - (j+1)
        # L_tmp = L[j+1:]
        # cnt += np.sum(L_tmp < b+a)

print(cnt)
### BUGGY CODE ###

from collections import Counter

s = list(input())
ls = len(s)
T = [0] * (ls+1)
modL = [0]
cnt = 0

for i in reversed(range(0, ls)):
    T[i] = T[i+1] + int(s[i]) * 10**(ls-i-1)
    modL.append(T[i] % 2019)

ans = 0
for c in Counter(modL).values():
    ans += c * (c - 1) // 2

print(ans)


### FIXED CODE ###

from collections import Counter

s = list(input())
ls = len(s)
T = [0] * (ls+1)
modL = [0]
cnt = 0
pad = 1

for i in reversed(range(0, ls)):
    T[i] = T[i+1] + int(s[i]) * pad
    modL.append(T[i] % 2019)
    pad = pad * 10 % 2019

ans = 0
for c in Counter(modL).values():
    ans += c * (c - 1) // 2

print(ans)