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

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]


#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

import heapq

#flag=Trueは大きい方
def index(n,flag=True):
    if flag==True:
        if n==N-1:
            return 0
        else:
            return n+1
    else:
        if n==0:
            return N-1
        else:
            return n-1

N = I()
A = III()
B = III()

x = []
for i in range(N):
    heapq.heappush(x,[-B[i],i])

counter = 0

while x:
    i = x[0][1]
    b = -x[0][0]
    a = B[index(i,False)]
    c = B[index(i)]
    if b == A[i]:
        heapq.heappop(x)
        continue
    if b<A[i]:
        print(-1)
        exit()
    else:
        if b<=a+c:
            print(-1)
            exit()
        temp = (b-A[i])/(a+c)
        if temp == (b-A[i])//(a+c):
            heapq.heappop(x)
            B[i] = A[i]
            counter += int(temp)
        else:
            count = b//(a+c)
            b -= count*(a+c)
            heapq.heappushpop(x,[-b,i])
            B[i] = b
            counter += count

print(counter)

### FIXED CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]


#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

import heapq

N = I()
A = III()
B = III()

x = []
for i,b in enumerate(B):
    heapq.heappush(x,(-b,i))

counter = 0

while x:
    temp = heapq.heappop(x)
    i = temp[1]
    b = -temp[0]
    a = B[(i-1)%N]
    c = B[(i+1)%N]
    if b == A[i]:
        continue
    elif b<A[i]:
        print(-1)
        exit()
    else:
        d,m = divmod(b-A[i],a+c)
        if d==0:
            print(-1)
            exit()
        elif m == 0:
            B[i] = A[i]
            counter = counter+d
        else:
            B[i] = A[i]+m
            heapq.heappush(x,(-B[i],i))
            counter = counter+d

print(counter)
### BUGGY CODE ###

from heapq import heappop, heappush
N, M = map(int, input().split())
link = {i: [] for i in range(1, N+1)}
for _ in range(M):
    u, v = map(int, input().split())
    link[u].append(v)
S, T = map(int, input().split())

''' dijkstra '''
INF = 10 ** 9
vstd = {i: False for i in range(1, N+1)}
dist = {i: INF for i in range(1, N+1)}  # distance
# prev = {i: -1 for i in range(1, N+1)}  # for extract min cost path
pq = []
# initialize
dist[S] = 0
heappush(pq, (0, S))
while pq:
    _, u = heappop(pq)
    vstd[u] = True
    for v in link[u]:
        # if vstd[v]:
        #     continue
        for w in link[v]:
            # if vstd[w]:
            #     continue
            for x in link[w]:
                if vstd[x]:
                    continue
                if dist[u] + 1 < dist[x]:
                    dist[x] = dist[u] + 1
                    # prev[v] = u
                    heappush(pq, (dist[x], x))

print(dist[T] if dist[T] != INF else -1)


### FIXED CODE ###

from heapq import heappop, heappush
N, M = map(int, input().split())
link = {(i, j) : [] for i in range(1, N+1) for j in range(3)}
for _ in range(M):
    u, v = map(int, input().split())
    link[(u, 0)].append((v, 1))
    link[(u, 1)].append((v, 2))
    link[(u, 2)].append((v, 0))
S, T = map(int, input().split())

''' dijkstra '''
INF = 10 ** 9
vstd = {(i, j): False for i in range(1, N+1) for j in range(3)}
dist = {(i, j): INF for i in range(1, N+1) for j in range(3)}  # distance
# prev = {i: -1 for i in range(1, N+1)}  # for extract min cost path
pq = []
# initialize
dist[(S, 0)] = 0
heappush(pq, (0, (S, 0)))
while pq:
    _, u = heappop(pq)
    vstd[u] = True
    for v in link[u]:
        if vstd[v]:
            continue
        if dist[u] + 1 < dist[v]:
            dist[v] = dist[u] + 1
            # prev[v] = u
            heappush(pq, (dist[v], v))


print(dist[(T, 0)] // 3 if dist[(T, 0)] % 3 == 0 else -1)
### BUGGY CODE ###

import sys
import copy
input = sys.stdin.readline

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

A=[a for a in A if a<K]
L=len(A)

MIN=-1
MAX=L-1

while MIN!=MAX:

    x=(MIN+MAX+1)//2
    base=A[x]

    SET={base}
    flag=0
    
    for i in range(L):
        #print(x,i,SET)
        if i==x:
            continue
        a=A[i]
        NSET=copy.copy(SET)
        
        for j in SET:
            
            if K<=a+j<K+base:
                flag=1
                break
            elif a+j<K:
                NSET.add(a+j)

        if flag==1:
            #print(x,SET)
            MAX=x-1
            break

        SET=NSET

    else:
        MIN=x
        continue

print(MIN+1)

    


### FIXED CODE ###

import sys
import copy
input = sys.stdin.readline

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

SUM=0
for a in A:
    SUM+=a
    if SUM>=K:
        MAX_NO_NEED=a
        break

else:
    print(N)
    sys.exit()
        

MAX=A.index(MAX_NO_NEED)-1

A=[a for a in A if a<K]
L=len(A)

MIN=-1
MAX=min(MAX,L-1)

while MIN!=MAX:

    x=(MIN+MAX+1)//2
    base=A[x]

    SET={base}
    flag=0
    
    for i in range(L):
        #print(x,i,SET)
        if i==x:
            continue
        a=A[i]
        NSET=copy.copy(SET)
        
        for j in SET:
            
            if K<=a+j<K+base:
                flag=1
                break
            elif a+j<K:
                NSET.add(a+j)

        if flag==1:
            #print(x,SET)
            MAX=x-1
            break

        SET=NSET

    else:
        MIN=x
        continue

print(MIN+1)
### BUGGY CODE ###

def apc001_c():
    import sys
    readline = sys.stdin.buffer.readline
    n = int(input())

    lower = 0
    print(lower)
    sys.stdout.flush()
    # seat_low = str(input())
    seat_low = str(readline())
    if seat_low == 'Vacant': return

    upper = n-1
    print(upper)
    sys.stdout.flush()
    # seat_up = str(input())
    seat_up = str(readline())
    if seat_up == 'Vacant': return

    cnt = 0
    while upper - lower > 1:
        x = (upper + lower) // 2
        print(x)
        sys.stdout.flush()
        # s = str(input())
        s = str(readline())
        if s == seat_low: lower = x
        elif s == seat_up: upper = x
        else: return
        cnt += 1
        if cnt > 20: break

if __name__ == '__main__':
    apc001_c()

### FIXED CODE ###

def apc001_c():
    import sys
    n = int(input())

    def ask(x:int):
        print(x)
        sys.stdout.flush()
        res = str(input())
        return res

    lower = 0
    seat_low = ask(lower)
    if seat_low == 'Vacant': return

    upper = n-1
    seat_up = ask(upper)
    if seat_up == 'Vacant': return

    while upper - lower > 1:
        x = (upper + lower) // 2
        s = ask(x)
        if s == 'Vacant': return
        if x % 2 == 0:
            if s == seat_low: lower = x
            else: upper = x
        else:
            if s == seat_up: lower = x
            else: upper = x

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

#!/usr/bin/python3
# -*- coding: utf-8 -*-
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)

n = int(input())
a_list = list(map(int, input().split()))
flag1 = 1
ans2 = a_list[n - 1]
for i in range(n - 1):
    if a_list[i] == 1:
        ans2 = 1
        continue
    if ans2 != 1:
        ans2 = gcd(ans2,a_list[i])
    if flag1 == 1:
        for j in range(i + 1, n):
            if gcd(a_list[i], a_list[j]) != 1:
                flag1 = 0
                break

if flag1 == 1:
    print("pairwise coprime")
elif ans2 == 1:
    print("setwise coprime")
else:
    print("not coprime")

### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)

n = int(input())
a_list = list(map(int, input().split()))
a_list.sort()
ans2 = a_list[0]
for i in range(1, n):
    ans2 = gcd(ans2, a_list[i])
    if ans2 == 1:
        break

if ans2 != 1:
    print("not coprime")
else:
    flag = 1
    max_a = a_list[n - 1] + 1
    num_flag_list = [True] * max_a
    d_list = list(range(0, max_a))
    d_list[0] = 1
    num_flag_list[0] = num_flag_list[1] = False
    for i in range(2, int(max_a**0.5) + 1):
        if num_flag_list[i]:
            for j in range(i**2, max_a, i):
                if num_flag_list[j] == True:
                    num_flag_list[j] = False
                    d_list[j] = i
    p_set = set()
    for a in a_list:
        if a == 1:
            continue
        temp_p_set = set()
        while True:
            p = d_list[a]
            if p not in temp_p_set:
                if p in p_set:
                    flag = 0
                    break
            temp_p_set.add(p)
            p_set.add(p)
            a = a // p
            if a == 1:
                break
        if flag == 0:
            break
        
    if flag == 1:
        print("pairwise coprime")
    else:
        print("setwise coprime")
### BUGGY CODE ###

import sys
from collections import deque

def read():
    return sys.stdin.readline().rstrip()

def main():
    n, m, k = map(int, read().split())
    friend = [[] for _ in range(n)]
    block = [set() for _ in range(n)]
    potential = [set() for _ in range(n)]
    for _ in range(m):
        a, b = [int(i) - 1 for i in read().split()]
        friend[a].append(b)
        friend[b].append(a)
    for _ in range(k):
        c, d = [int(i) - 1 for i in read().split()]
        block[c].add(d)
        block[d].add(c)
    sd = set()
    for u in range(n):
        if u in sd:
            continue
        sn = deque([u])
        pf = set()
        while sn:
            p = sn.pop()
            if p in sd:
                continue
            sd.add(p)
            pf.add(p)
            for f in friend[p]:
                sn.append(f)
        for pfi in pf:
            potential[pfi] = pf
    print(*[len(potential[i] - block[i]) - len(friend[i]) - 1 for i in range(n)])

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from collections import deque

def read():
    return sys.stdin.readline().rstrip()

def main():
    n, m, k = map(int, read().split())
    friend = [[] for _ in range(n)]
    block = [set() for _ in range(n)]
    potential = [set() for _ in range(n)]
    for _ in range(m):
        a, b = [int(i) - 1 for i in read().split()]
        friend[a].append(b)
        friend[b].append(a)
    for _ in range(k):
        c, d = [int(i) - 1 for i in read().split()]
        block[c].add(d)
        block[d].add(c)
    sd = set()
    for u in range(n):
        if u in sd:
            continue
        sn = deque([u])
        pf = set()
        while sn:
            p = sn.pop()
            if p in sd:
                continue
            sd.add(p)
            pf.add(p)
            for f in friend[p]:
                sn.append(f)
        for pfi in pf:
            potential[pfi] = pf
    print(*[len(potential[i]) - len(block[i] & potential[i]) - len(friend[i]) - 1 for i in range(n)])

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

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

p_kitai = []
max = 0
max2 = 0

for i in range(len(p)):
    p_kitai.append(sum(range(1,p[i]+1))/p[i])
    
for i in range(len(p)-K+1):
    k = i
    for j in range(K):
        max += p_kitai[k]
        k += 1
    if max > max2:
        max2 = max
        max = 0
    else:
        max = 0
        
print(max2)

### FIXED CODE ###

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

value = [0]*N
k_list = []

for i in range(N):
    value[i] = (p[i]+1)*0.5
    
value_list = [0]*N

for i in range(N):
    value_list[i] = value_list[i-1] + value[i]

value_list.append(0)

for i in range(N-K+1):
    k_list.append(value_list[i+K-1]-value_list[i+K-(K+1)])
    
print(max(k_list))
### BUGGY CODE ###

K,N=map(int, input().split())
A=list(map(int, input().split()))
max_diff = 0
for i in range(0,N):
    for j in range(i,N):
        ck = abs(A[j] - A[i])
        if max_diff < ck:
            if ck <= K/2:
                max_diff = ck
print(max_diff)


### FIXED CODE ###

K,N=map(int, input().split())
A=list(map(int, input().split()))
max_diff = 0
ck = 0
for i in range(0,N):
    if i == N -1:
        ck = abs(A[(i+1)%N] + K  - A[i])
    else:
        ck = abs(A[(i+1)%N] - A[i])
    if max_diff < ck:
        max_diff = ck
print(K - max_diff)
### BUGGY CODE ###

import copy
N, K = map(int, input().split())
A = list(map(int, input().split()))
A2 = copy.copy(A)
for i in range(K):
    for t in range(N):
        b = 0
        for j in range(N):
            if t+1 <= (j+1+A[j]+0.5) and (j+1-A[j]-0.5) <= t+1:
                b+=1
        A2[t]=b
    A=copy.copy(A2)

print(*A)

### FIXED CODE ###

import math
N, K = map(int, input().split())
A = list(map(int, input().split()))
A2 = [0]*(N+1)
for i in range(K):
    for j in range(N):
        g = math.ceil(j+1-A[j]-0.5)
        if g<1:
            g=1
        h = math.floor(j+1+A[j]+0.5)
        if h>N:
            h=N
        A2[g-1]+=1
        A2[h]-=1
    A[0]=A2[0]
    for j in range(1, N):
        A[j]=A[j-1]+A2[j]
    A2 = [0]*(N+1)
    c = 0
    for p in range(N):
        c+=A[p]
    if c >= N*N:
        break

print(*A)
### BUGGY CODE ###

A, B, N = map(int,input().split())
bst = -100000000

for i in range(N+1):
  ans = (A*i)//B - A*(i//B)
  if (ans > bst):
    bst = ans

print(bst)

### FIXED CODE ###

A,B,N = map(int, input().split())
p = min(N,B)

if p%B == 0:
    print(int(A*(p-1)//B))
else :
    print(int(A*(p)//B))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

YES = "YES"  # type: str
NO = "NO"  # type: str

def solve(S: str):
    while len(S)>4:
        if S[:11]=="dreameraser":
            S=S[11:]
        elif S[:10] == "dreamerase":
            S= S[10:]
        elif S[:6]=="eraser":
            S= S[6:]
        elif S[:5] == "erase" or S[:5]== "dream":
            S=S[5:]
        elif S[:7] == "dreamer":
            S=S[7:]
        else:
            print(NO)
        
    
    if len(S) == 0:
        print(YES)
    else:
        print(NO)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

if __name__ == '__main__':
    main()



### FIXED CODE ###

#!/usr/bin/env python3
import sys

YES = "YES"  # type: str
NO = "NO"  # type: str

def solve(S: str):
    S = S[::-1]
    while len(S)>4:
        if S[:6]=="resare":
            S= S[6:]
        elif S[:5] == "esare" or S[:5]== "maerd":
            S=S[5:]
        elif S[:7] == "remaerd":
            S=S[7:]
        else:
            print(NO)
            return 
        
    
    if len(S) == 0:
        print(YES)
    else:
        print(NO)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

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

N = int(input())
array = list(map(int, input().split()))
ans = 0
for i in range(N):
    for k in range(i,N):
        for j in range(k,N):
            if i != k and k != j and j != i:
                if (array[i] < array[k] + array[j]) and (array[j] < array[i] + array[k]) and (array[k] < array[i] + array[j]):
                    ans += 1
print(ans)

### FIXED CODE ###

import bisect
N = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
for i in range(N):
    for k in range(i+1,N):
        tmp = bisect.bisect_left(a,a[i]+a[k])
        ans += tmp - k - 1
print(ans)
### BUGGY CODE ###

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

a, b = [int(x) for x in input().split()]

d = 1
d_list = []
while(d <= a and d <= b):
  if a % d == 0 and b % d == 0:
    d_list.append(d)
  d += 1

length = len(d_list)

x = prime_factorize(d_list[-1])
print(len(set(x))+1)

### FIXED CODE ###

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

a, b = [int(x) for x in input().split()]
from fractions import gcd

x = gcd(a,b)

x = prime_factorize(x)
print(len(set(x)) + 1)
### BUGGY CODE ###

import math
n = int(input())
mx = 1000000000
if n<mx:
    print(0, 0, 1, 0, 1, n)
else:
    l=1
    r=mx
    start = n
    while(start>mx):
        next = (l+r)//2
        start = n // next
        if start > mx:
            if next!=l:
                l = next
            else:
                l+=1
    for i in range(start,n+1):
        if n%i==0:
            ret = n//i
            if ret<=mx:
                break
    print(0,0,i,0,i,ret)


### FIXED CODE ###

import math
n = int(input())
mx = 1000000000
# mx = 7
if n<mx:
    print(0, 0, 1, 0, 1, n)
else:
    mul = math.ceil((n*1.0)/mx)
    x3= mx*mul-n
    print(0,0,mx,1,x3,mul)
### BUGGY CODE ###

n=int(input())
i=0
while(1):
    n//=2
    i+=1
    if n==1:
        break
i=bin(i+1)[2:]
ans=1
mkr=2
for j in i[::-1]:
    if j=="1":
        ans*=mkr
    mkr*=mkr
print(ans-1)

### FIXED CODE ###

n=int(input())
i=0
while(1):
    if n==1:
        break
    n//=2
    i+=1
i=bin(i+1)[2:]
ans=1
mkr=2
for j in i[::-1]:
    if j=="1":
        ans*=mkr
    mkr*=mkr
print(ans-1)
### BUGGY CODE ###

h,w=map(int,input().split())
l=[list(map(str,input())) for _ in range(h)]  
def maze(MAZE,sx,sy,gx,gy):
  dmap=[[h*w]*w for _ in range(h)]
  dmap[sx][sy]=0
  dist=h*w
  cand=[]
  visited=set()
  if sx==gx and sy==gy:
    dist=0
  else:
    cand.append([sx,sy])
  while len(cand)!=0:
    x,y=cand.pop()
    visited.add((x,y))
    for next_y,next_x in [(y+1, x), (y, x+1), (y, x-1), (y-1, x)]:
      if next_x==gx and next_y==gy:
        if dist>dmap[x][y]+1:
          dist=dmap[x][y]+1
        break
      elif 0<=next_x<=h-1 and 0<=next_y<=w-1 and MAZE[next_x][next_y]=='.' and not (next_x,next_y) in visited:
        cand.append([next_x,next_y])
        dmap[next_x][next_y]=min(dmap[x][y]+1,dmap[next_x][next_y])
  return dist
c=0
for ix in range(h):
  for iy in range(w):
    if l[ix][iy]!='#':
      for jx in range(h):
        for jy in range(w):
          if l[jx][jy]!='#':
            d=maze(l,ix,iy,jx,jy)
            if c<d:
              c=d
print(c)

### FIXED CODE ###

from collections import deque
h,w=map(int,input().split())
l=[list(map(str,input())) for _ in range(h)]  
def maze(MAZE,sx,sy):
  dmap=[[h*w]*w for _ in range(h)]
  dmap[sx][sy]=0
  cand=deque()
  cand.append([sx,sy])
  while len(cand)!=0:
    x,y=cand.popleft()
    for next_y,next_x in [(y+1, x), (y, x+1), (y, x-1), (y-1, x)]:
      if 0<=next_x<=h-1 and 0<=next_y<=w-1 and MAZE[next_x][next_y]=='.' and dmap[next_x][next_y]==h*w:
        dmap[next_x][next_y]=min(dmap[x][y]+1,dmap[next_x][next_y])
        cand.append([next_x,next_y])
  return max([dmap[i][j] for i in range(h) for j in range(w) if dmap[i][j]<h*w])
c=0
for ix in range(h):
  for iy in range(w):
    if l[ix][iy]!='#':
      d=maze(l,ix,iy)
      if c<d:
        c=d
print(c)
### BUGGY CODE ###

import sys
from math import factorial
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

n, k = MAP()
a = LIST()

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

a.sort(reverse = True)
res = 0
for i in range(n-k+1):
    res += a[i] * cmb(n-i-1, k-1)

a.reverse()
for i in range(n-k+1):
    res -= a[i] * cmb(n-i-1, k-1)

print(res%MOD)

### FIXED CODE ###

import sys
from math import factorial
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

n, k = MAP()
a = LIST()

def mpow(a, n):
    if n == 0:return 1
    if n == 1:return a%MOD
    if n%2 == 1:return (a%MOD * mpow(a, n-1)%MOD)%MOD
    t = mpow(a, n//2)
    return (t*t)%MOD

fac = [1]*(n+1)
inv_fac = [1]*(n+1)
for i in range(n):
    fac[i+1] = (fac[i]*(i+1))%MOD
inv_fac[n] = mpow(fac[n], MOD-2)
for i in range(n, 0, -1):
    inv_fac[i-1] = (inv_fac[i]*i)%MOD

def cmb(n, r):
    if n == 0 and r == 0:return 1
    if n<r or n<0:return 0
    return (fac[n]*(inv_fac[r]*inv_fac[n-r])%MOD)%MOD
 
a.sort(reverse = True)
res = 0
for i in range(n-k+1):
    res += (a[i]*cmb(n-i-1, k-1))%MOD
    res = res%MOD
 
a.reverse()
for i in range(n-k+1):
    res -= (a[i]*cmb(n-i-1, k-1))%MOD
    res = res%MOD
 
print(res)
### BUGGY CODE ###

N,K = map(int,input().split())
S = list(map(int,input()))
tmp = 1
nums = []
cont = 0
for s in S:
    if int(s) == tmp:
        cont += 1
    else:
        nums.append(cont)
        cont = 1
        tmp = 1 - tmp
if cont != 0:
    nums.append(cont)
if len(nums) % 2 == 0:
    nums.append(0)
ans = 0
lst = []
for i in range(0,len(nums),2):
    for j in range(i,min(i+K*2+1,len(nums))):
        ans += nums[j]
    lst.append(ans)
    ans = 0
print(max(lst))

### FIXED CODE ###

N,K = map(int,input().split())
S = list(map(int,input()))
tmp = 1
nums = []
cont = 0
for s in S:
    if int(s) == tmp:
        cont += 1
    else:
        nums.append(cont)
        cont = 1
        tmp = 1 - tmp
if cont != 0:
    nums.append(cont)
if len(nums) % 2 == 0:
    nums.append(0)
cml = [0]
for n in nums:
    cml.append(cml[-1]+n)
ans = []
for i in range(0,len(cml),2):
    ans.append(cml[min(len(cml)-1,i+K*2+1)]-cml[i])
print(max(ans))
### BUGGY CODE ###

import numpy as np
s=input()
ss=[]
for i in range(len(s)):
    ss.append(s[i])

    
arr=np.array(ss)

q=int(input())
for i in range(q):
    l=list(map(str,input().split()))
    if l[0]=="1":
        arr=arr[::-1]
        
    else:
        if l[1]=="1":
            arr=arr[::-1]
            arr=np.append(arr,l[2])
            arr=arr[::-1]
        if l[1]=="2":
            arr=np.append(arr,[l[2]])
        

a=arr.tolist()
for i in a:
    print(i,end="")

### FIXED CODE ###


s=input()
q=int(input())
p=0
a=""
b=""
for i in range(q):
    l=list(map(str,input().split()))
    if l[0]=="1":
        p=(p+1)%2
    else:
        if p==0:
            if l[1]=="1":
                a+=l[2]
            else:
                b+=l[2]
        else:
            if l[1]=="1":
                b+=l[2]
            else:
                a+=l[2]
if p==1:
    print(b[::-1]+s[::-1]+a)
else:
    print(a[::-1]+s+b)