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

N, K = map(int, input().split())
h = list(map(int, input().split()))
INF = 10**9+10

c = [INF] * N
c[0] = 0

for i in range(N):
  for j in range(1, min(K, i)+1):
    c[i] = min(c[i], c[i-j]+abs(h[i]-h[i-j]))
print(c[-1])

### FIXED CODE ###

N, K = map(int, input().split())
h = [int(i) for i in input().split()]
INF = 10**9

c = [INF] * N
c[0] = 0

for i in range(N):
  tmp = []
  for j in range(1, min(K, i)+1):
    c[i] = min(c[i-j] + abs(h[i] - h[i-j]), c[i])
print(c[-1])
### BUGGY CODE ###

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

total = 0
for i in range(n-1):
    for j in range(i+1, n):
        total += (a[i] * a[j]) % 1000000007

print(total % 1000000007)


### FIXED CODE ###

mod = 1000000007

n = int(input())
a = list(map(int, input().split(' ')))
b = [0] * (n + 1)

for i, v in enumerate(a):
    b[i+1] = (b[i] + v) % mod

ans = 0
for i in range(n):
    ans = (((a[i] * (b[n] - b[i+1])) % mod) + ans) % mod

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

from math import gcd


def lcm(a, b):
    return a * b // gcd(a, b)


def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        if n % b == 0:
            fct.append(b)
        while n % b == 0:
            n //= b
        b = b + 1
    if n > 1:
        fct.append(n)
    return set(fct)


n = int(input())
a = list(map(int, input().split()))
g = a[0]
l = a[0]

new_a = list(map(factorize, a))
#print(new_a)
wa = new_a[0]
cnt = 0
flag = 1
for i in range(1, n):
    if gcd(l, a[i]) > 1:
        flag = 0
    g = gcd(g, a[i])
    l = lcm(l, a[i])
if g > 1:
    print("not coprime")
elif flag == 0:
    print("setwise coprime")
else:
    print("pairwise coprime")

# for i in range(1, n):
#     b = gcd(b, a[i])
#     if b == 1:
#         break
# else:
#     print("not coprime")
#     exit()
#
# new_a = list(map(factorize, a))
# wa = new_a[0]
# cnt = 0
# flag = 0
# for i in range(1, n):
#     if len(wa & new_a[i]) > 0 and flag == 0:
#         flag = 1
#         break
#     wa = wa | new_a[i]
#
# if flag:
#     print("setwise coprime")
# else:
#     print("pairwise coprime")



### FIXED CODE ###

import math


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 set(a)


n = int(input())
a = list(map(int, input().split()))
num = a[0]
for i in range(1, n):
    num = math.gcd(num, a[i])
if num != 1:
    print("not coprime")
    exit()
prime_memo = {}
for i in range(n):
    prime_number = prime_factorize(a[i])
    for num in prime_number:
        if num not in prime_memo.keys():
            prime_memo[num] = 1
        else:
            print("setwise coprime")
            exit()
print("pairwise coprime")
### BUGGY CODE ###

N, M = map(int, input().split())
A = [0] * M
B = [0] * M
C = []
for m in range(M):
    A[m], B[m] = map(int, input().split())
    C.append(set([int(cm) for cm in input().split()]))

INF = 100000000
dp = [[INF] * 2**N for _ in range(M + 1)]
dp[0][0] = 0


def Set2Bit(st):
    bt = ["0"]*N
    for i in st:
        bt[i-1] = "1"
    return bt


for m in range(0, M):
    key = Set2Bit(C[m])
    key_bit = int("".join(key), 2)
    for bit in range(2**N):
        pre_bit = next_bit = bit
        dp[m+1][next_bit] = dp[m][pre_bit]
    for bit in range(2**N):
        pre_bit = bit
        next_bit = pre_bit | key_bit
        dp[m+1][next_bit] = min(dp[m+1][next_bit], dp[m][next_bit], dp[m][pre_bit] + A[m])

if dp[-1][-1] == INF:
    print(-1)
else:
    print(dp[-1][-1])

### FIXED CODE ###

N, M = map(int, input().split())
A = [0] * M
B = [0] * M
C = [0]*M
for m in range(M):
    A[m], B[m] = map(int, input().split())
    C[m] = [int(cm) for cm in input().split()]

INF = 100000000
dp = [[INF] * 2**N for _ in range(M + 1)]
dp[0][0] = 0


def Set2Bit(st):
    bt = ["0"]*N
    for i in st:
        bt[i-1] = "1"
    return bt


for m in range(0, M):
    key = Set2Bit(C[m])
    key_bit = int("".join(key), 2)
    for bit in range(2**N):
        pre_bit = next_bit = bit
        dp[m+1][next_bit] = dp[m][pre_bit]
    for bit in range(2**N):
        pre_bit = bit
        next_bit = pre_bit | key_bit
        dp[m+1][next_bit] = min(dp[m+1][next_bit], dp[m][next_bit], dp[m][pre_bit] + A[m])

if dp[-1][-1] == INF:
    print(-1)
else:
    print(dp[-1][-1])
### BUGGY CODE ###

N = int(input())
print(sum([i for i in range(1,N+1)])-N)


### FIXED CODE ###

N = int(input())
print(int(N*(N-1)//2))
### BUGGY CODE ###

N = int(input())

count = 0

for i in range(N - 1):
    A = i + 1
    for j in range(N-1):
        B = j + 1

        if A * B < N:
            count += 1
        else:
            break

print(count)

### FIXED CODE ###

N = int(input())

count = 0

for i in range(N - 1):
    A = i + 1
    B = N / A

    if B == int(B):
        count += B-1
    else:
        count += int(B)

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

class Solver(object):
    def __init__(self):
        self.n = int(input())
        self.a_s = list(map(int, input().split(" ")))
        self._sadness = {}

    def solve(self):
        b = 0
        current = self.sadness(b)
        left = self.sadness(b-1)
        right = self.sadness(b+1)
        reset_counter = 0
        momentum = 1
        previous = 0  # -1 => left, 1 = right
        while True:
            # print("{}: {} {} {}".format(b, left, current, right))
            if (left >= current) and (right >= current):
                print(current)
                return
            elif left < right:  # go left
                if reset_counter < 4:
                    if previous == -1:
                        momentum *= 3
                    else:
                        reset_counter += 1
                        momentum = 1
                    previous = -1
                b -= momentum
            else:  # go right
                if reset_counter < 4:
                    if previous == 1:
                        momentum *= 3
                    else:
                        reset_counter += 1
                        momentum = 1
                    previous = 1
                b += momentum
            current = self.sadness(b)
            left = self.sadness(b-1)
            right = self.sadness(b+1)
        
    def sadness(self, b):
        if b not in self._sadness:
            self._sadness[b] = sum(abs(self.a_s[i] - (b+i+1)) for i in range(self.n))
        return self._sadness[b]


if __name__ == "__main__":
    s = Solver()
    s.solve()

### FIXED CODE ###

class Solver(object):
    def __init__(self):
        self.n = int(input())
        self.a_s = list(map(int, input().split(" ")))
        self._sadness = {}

    def solve(self):
        array = self.a_s.copy()
        for i in range(self.n):
            array[i] -= i + 1
        array.sort()
        b = array[len(array) // 2]
        print(self.sadness(b))
        
    def sadness(self, b):
        if b not in self._sadness:
            self._sadness[b] = sum(abs(self.a_s[i] - (b+i+1)) for i in range(self.n))
        return self._sadness[b]


if __name__ == "__main__":
    s = Solver()
    s.solve()
### BUGGY CODE ###

a, v = map(int, input().split())
b, w = map(int, input().split())
t = int(input())
ans = 'NO'
for i in range(t):
    if a < b:
        a += v
        b += w
    else:
        a -= v
        b -= w
    if a == b:
        ans = 'YES'
        break
print(ans)

### FIXED CODE ###

a, v = map(int, input().split())
b, w = map(int, input().split())
t = int(input())
if abs(a - b) <= (v -w) * t:
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

from collections import Counter

N = int(input())


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


count = 0
for c in range(1, N):
    d = Counter(prime_factorize(N - c))

    tmp = 1
    for x in d.values():
        tmp *= x + 1
    count += tmp

print(count)


### FIXED CODE ###

N = int(input())
ans = 0
for a in range(1, N):
    ans += (N-1) // a
print(ans)
### BUGGY CODE ###

inr = lambda: list(map(int, input().split()))
inn = lambda: input()

N,Q = inr()
S = inn()
for q in range(Q):
    l,r = inr()
    bubun = S[l-1:r]
    print(bubun.count("AC"))

### FIXED CODE ###

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

# https://atcoder.jp/contests/abc065/tasks/arc076_a

import itertools
from collections import Counter
from collections import defaultdict
import bisect
import math
import heapq

def main():
    N, M = map(int, input().split())

    mod = 10**9 + 7

    if abs(N - M) > 1:
        print(0)
        exit()

    n = 1
    for i in range(1, N + 1):
        n *= i
    m = 1
    for i in range(1, M + 1):
        m *= i

    if N == M:
        print((n * m * 2) % mod)
    else:
        print((n * m) % mod)

if __name__ == '__main__':
    main()


### FIXED CODE ###

# https://atcoder.jp/contests/abc065/tasks/arc076_a

import itertools
from collections import Counter
from collections import defaultdict
import bisect
import math
import heapq

def main():
    N, M = map(int, input().split())

    mod = 10**9 + 7

    if abs(N - M) > 1:
        print(0)
        exit()

    n = 1
    m = 1
    for i in range(1, N + 1):
        n = (n * i) % mod
    for i in range(1, M + 1):
        m = (m * i) % mod

    if N == M:
        print((n * m * 2) % mod)
    else:
        print((n * m) % mod)

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

def lucas(n):
     if n == 0:
         return 2
     elif n == 1:
         return 1
     else:
         return lucas(n-1)+lucas(n-2)
n = int(input().strip())
print(lucas(n))

### FIXED CODE ###

memo = [0]*100
memo[0] = 2
memo[1] = 1
def lucas(n):
     if memo[n] != 0:
         return memo[n]
     else:
         memo[n] = lucas(n-1)+lucas(n-2)
         return memo[n] 
n = int(input().strip())
print(lucas(n))
### BUGGY CODE ###

s = str(input())

num = [int(s[-1])]
for i in range(1, len(s)):
    num.append(num[-1] + pow(10, i) * int(s[-i - 1]))

mod = [1] + [0] * 2018
ans = 0
for i in num:
    m = i % 2019
    ans += mod[m]
    mod[m] += 1
print(ans)


### FIXED CODE ###

s = str(input())

num = [int(s[-1])]
for i in range(1, len(s)):
    tmp = num[-1] + pow(10, i, 2019) * int(s[-i - 1])
    num.append(tmp % 2019)

mod = [1] + [0] * 2018
ans = 0
for i in num:
    m = i % 2019
    ans += mod[m]
    mod[m] += 1
print(ans)
### BUGGY CODE ###

K=int(input())

j=0
ans=0
a=0
while True:
    a=a*10+7
    ans+=1
    if a%K==0:
        break
    
    if ans>K:
        ans=-1
        break

print(ans)

### FIXED CODE ###

K=int(input())
 
j=0
ans=0
a=0
while True:
    a=a*10+7
    a=a%K
    ans+=1
    
    if a==0:
        break
    
    if ans>K:
        ans=-1
        break
 
print(ans)
### BUGGY CODE ###

from bisect import insort_left

Q = int(input())
Query = [input() for _ in range(Q)]

x = []
c = 0
i = 0

for q in Query :

    if q[0] == '1' :
        a, b = map(int, q[2:].split())
        
        insort_left(x, a)
        c += b
        i += 1

    else :
        min_v = float('inf')

        mid_l, mid_r = (i - 1) // 2, i // 2
        for mid in range(mid_l, mid_r + 1) :
            tmp = 0
            xmid = x[mid]

            for xi in x :
                tmp += abs(xi - xmid)
            
            if tmp < min_v :
                min_v = tmp
                min_k = x[mid]
        
        print(min_k, min_v + c)


### FIXED CODE ###

import heapq

Q = int(input())
Query = [input() for _ in range(Q)]

ans = 0

lq = []
rq = []

for q in Query :
    if q[0] == '1' :
        a, b = map(int, q[2:].split())
        
        heapq.heappush(lq, -a)
        heapq.heappush(rq, a)

        lmax, rmin = -heapq.heappop(lq), heapq.heappop(rq)
        if lmax > rmin :
            lmax, rmin = rmin, lmax
            ans += rmin - lmax

        heapq.heappush(lq, -lmax)
        heapq.heappush(rq, rmin)

        ans += b

    else :
        print(-lq[0], ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
count = 0
for i in range(n-1):
	for j in range(i+1,n):
		count += a[i]*a[j]
print(count%(10**9+7))

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
count = 0
su = sum(a)
for i in range(n-1):
	su -= a[i]
	count += a[i]*su
print(count%(10**9+7))
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10000)
INF = float('inf')

H, W = list(map(int, input().split()))
A = [list(input()) for _ in range(H)]


def ok(h, w):
    return 0 <= h < H and 0 <= w < W


hw = set()
for h in range(H):
    for w in range(W):
        if A[h][w] == '#':
            if ok(h, w) and A[h][w] == '#':
                hw.add((h, w))

ans = -1
while len(hw) > 0:
    ans += 1
    nexts = set()
    for h, w in hw:
        if ok(h + 1, w) and A[h + 1][w] == '.':
            A[h + 1][w] = '#'
            nexts.add((h + 1, w))
        if ok(h - 1, w) and A[h - 1][w] == '.':
            A[h - 1][w] = '#'
            nexts.add((h - 1, w))
        if ok(h, w + 1) and A[h][w + 1] == '.':
            A[h][w + 1] = '#'
            nexts.add((h, w + 1))
        if ok(h, w - 1) and A[h][w - 1] == '.':
            A[h][w - 1] = '#'
            nexts.add((h, w - 1))
    hw = nexts
print(ans)


### FIXED CODE ###

import sys
import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')

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

counts = np.zeros((H, W))
counts[A == '.'] = np.inf

for h in range(1, H):
    counts[h, :] = np.minimum(counts[h, :], counts[h - 1, :] + 1)
    counts[-1 - h, :] = np.minimum(counts[-1 - h, :], counts[-h, :] + 1)
for w in range(1, W):
    counts[:, w] = np.minimum(counts[:, w], counts[:, w - 1] + 1)
    counts[:, -1 - w] = np.minimum(counts[:, -1 - w], counts[:, -w] + 1)

print(int(np.max(counts)))
### BUGGY CODE ###

import math

def gcd(a, b, c):
    g = math.gcd(a, b)
    return math.gcd(g, c)

K = int(input())
sum = 0

for i in range(1, K+1):
    for j in range(1, K+1):
        for k in range(1, K+1):
            sum += gcd(i, j, k)
print(sum)


### FIXED CODE ###

from math import gcd

def gcd_3(a, b, c):
    g = gcd(a, b)
    return gcd(g, c)

K = int(input())
ans = 0

for i in range(1, K+1):
    for j in range(1, K+1):
        for k in range(1, K+1):
            ans += gcd_3(i, j, k)

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

n,k = map(int,input().split())
p = list(map(int,input().split()))

ls = []
for i in range(n-k+1):
    ans = 0
    for j in range(k):
        for l in range(p[i+j]):
            ans += (1/p[i+j]*(l+1))
    ls.append(ans)
    
print(max(ls))
        

### FIXED CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))

ls = []
ans = 0

for i in range(k):
    ans += p[i]
    
max_ans = ans
max_index = 0

for i in range(n-k):
    ans -= p[i]
    ans += p[i+k]
    if max_ans < ans:
        max_ans = ans
        max_index = i+1

ans = 0
for i in range(k):
    pp = p[max_index+i]
    for j in range(pp):
        ans += (1/pp*(j+1))
    
print(ans)
### BUGGY CODE ###

N = int(input())
p, score = 2, 0
while p <= N:
  e = 1
  while p ** e <= N:
    # print(p, e, N, score)
    if N % (p ** e):
      break
    else:
      N = N // (p ** e)
      score += 1
      e += 1
      # print('tasu')
      # print(p, e, N, score)
  else:
    p += 1
print(score)

### FIXED CODE ###

N = int(input())
n, p, score = N, 2, 0
while p ** 2 <= N:
  e = 1
  # print(n, p, e)
  while n >= (p ** e) and n % (p ** e) == 0:
    n = n // (p ** e)
    score += 1
    e += 1
  else:
    while n >= p and n % p == 0:
      n = n // p
    p = p + 1 if p == 2 else p + 2
else:
  if n != 1:
    score += 1
print(score)
### BUGGY CODE ###

mod = 1000000007
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
# print(a)
ans = 0
dp = [0 for _ in range(n+1)]
dp[0] = 1
for i in range(n):
    if i in a:
        continue
    if i + 1 <= n:
        dp[i+1] += dp[i]
    if i + 2 <= n:
        dp[i+2] += dp[i]
# print(dp)
print(dp[n] % mod)

### FIXED CODE ###

MOD = 10 ** 9 + 7
n, m = map(int, input().split())
broken = [False] * (n + 1)
for i in range(m):
    a = int(input())
    broken[a] = True
dp = [0] * (n+1)
dp[0] = 1
for i in range(n):
    dp[i] %= MOD
    if broken[i]:
        dp[i] = 0
    if i + 1 <= n:
        dp[i+1] += dp[i]
    if i + 2 <= n:
        dp[i+2] += dp[i]
print(dp[n] % MOD)
### BUGGY CODE ###

ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())


def main():
    import numpy as np
    N,K = mis()
    A = np.array(lmis())
    l = np.zeros(N+1, dtype=np.int64)
    for _ in range(K):
        l[:] = 0
        for i in range(N):
            a = A[i]
            l[max(0, i-a)] += 1
            l[min(N, i+a+1)] -= 1
        A = l.cumsum()[:-1]
        if np.all(A==N):
            break
    print(*A)

main()



### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain, accumulate
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    N,K = mis()
    A = lmis()
    for _ in range(K):
        l = [0]*(N+1)
        for i in range(N):
            a = A[i]
            l[max(0, i-a)] += 1
            l[min(N, i+a+1)] -= 1
        A = list(accumulate(l))[:-1]
        if all(a==N for a in A):
            break
    print(*A)

main()
### BUGGY CODE ###

h,w = map(int,input().split(" "))
s = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    tmp = list(input())
    for j in range(w):
        s[i][j] = tmp[j]
dp1 = [[-1 for i in range(w)] for j in range(h)]
dp2 = [[-1 for i in range(w)] for j in range(h)]
dp3 = [[-1 for i in range(w)] for j in range(h)]
dp4 = [[-1 for i in range(w)] for j in range(h)]

for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            dp1[i][j] = 0
        elif j == 0:
            dp1[i][j] = 1
        else:
            dp1[i][j] = 1 + dp1[i][j-1]

for i in range(h):
    for j in range(w-1,-1,-1):
        if s[i][j] == "#":
            dp2[i][j] = 0
        elif j == w-1:
            dp2[i][j] = 1
        else:
            dp2[i][j] = 1 + dp2[i][j+1]

for i in range(w):
    for j in range(h):
        if s[j][i] == "#":
            dp3[j][i] = 0
        elif j == 0:
            dp3[j][i] = 1
        else:
            dp3[j][i] = 1 + dp3[j-1][i]

for i in range(w):
    for j in range(h-1,-1,-1):
        if s[j][i] == "#":
            dp4[j][i] = 0
        elif j == h-1:
            dp4[j][i] = 1
        else:
            dp4[j][i] = 1 + dp4[j+1][i]

a = 1
for i in range(h):
    for j in range(w):
        a = max(a,dp1[i][j]+dp2[i][j]+dp3[i][j]+dp4[i][j]-3)

print(a)

### FIXED CODE ###

h,w = map(int,input().split(" "))
s = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    tmp = list(input())
    for j in range(w):
        s[i][j] = tmp[j]

dp1= []
dp2= [[-1 for i in range(w)] for j in range(h)]
dp3=[]
dp4=[[-1 for i in range(w)] for j in range(h)]


for i in range(h):
    dp1.append([])
    dp3.append([])
    for j in range(w):
        dp1[i].append(-1)
        dp3[i].append(-1)

        if s[i][j] == "#":
            dp1[i][j] = 0
        elif j == 0:
            dp1[i][j] = 1
        else:
            dp1[i][j] = 1 + dp1[i][j-1]

        if s[i][w-j-1] == "#":
            dp2[i][w-j-1] = 0
        elif w-j-1 == w-1:
            dp2[i][w-j-1] = 1
        else:
            dp2[i][w-j-1] = 1 + dp2[i][w-j]

        if s[i][j] == "#":
            dp3[i][j] = 0
        elif i == 0:
            dp3[i][j] = 1
        else:
            dp3[i][j] = 1 + dp3[i-1][j]

        if s[h-i-1][j] == "#":
            dp4[h-i-1][j] = 0
        elif h-i-1 == h-1:
            dp4[h-i-1][j] = 1
        else:
            dp4[h-i-1][j] = 1 + dp4[h-i][j]



        

a = 1
for i in range(h):
    for j in range(w):
        a = max(a,dp1[i][j]+dp2[i][j]+dp3[i][j]+dp4[i][j]-3)


print(a)
### BUGGY CODE ###

n,m = map(int,input().split())
ans = 0
tmp = 1
while True:
    num = m - tmp*(n-1)
    if num < tmp:
        break
    elif num % tmp == 0:
        ans = tmp
    tmp += 1
print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
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)
    return divisors
ans = 1
lst = make_divisors(m)
lst.sort()
for d in lst:
    if m>=d*n:
        ans = d
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import collections
import itertools as it
import math
#import numpy as np
 
s  = input()
n  = int(input())
#  = map(int, input().split())
#  = list(map(int, input().split()))
#  = [int(input()) for i in range(N)]
#
# c = collections.Counter()

for _ in range(n):
    ipt = input()

    if ipt[0] == '1':
        s = s[::-1]
    else:
        _, id_, s_ = ipt.split()
        if id_ == '1':
            s = s_ + s
        else:
            s = s + s_

print(s)


### FIXED CODE ###

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

s_mae = ''
s_ato = s

for _ in range(n):
    ipt = input()

    if ipt[0] == '1':
        s_mae, s_ato = s_ato, s_mae
    else:
        _, id_, s_ = ipt.split()
        is_head = True if id_ == '1' else False
        if is_head:
            s_mae += s_
        else:
            s_ato += s_

print(s_mae[::-1] + s_ato)