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

def main():
    s = input()
    n = int(input())
    for _ in range(n):
        head = ''
        tail = ''
        q = input()
        if q[0] == '1':
            s = s[::-1]
        else:
            _, f, c = q.split()
            if f == '1':
                head = c
            else:
                tail = c
        s = head + s + tail
    return s
print(main())


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read

#h,w,k = [int(i) for i in read().split()]


s = input()
u = ""
t = ""
q = int(input())
num = 0

for _ in range(q):
    a = readline().split()
    if len(a)==1:
        u,t = t,u
        num ^= 1
    else:
        f = int(a[1])
        c = a[2]
        if f==1:
            t += c
        else:
            u += c

if num:
    print(t[::-1]+s[::-1]+u)
else:
    print(t[::-1]+s+u)
### BUGGY CODE ###

N, M = map(int, input().split())
mod = 1000000007
dp = [0] * (N+2)
A = [int(input()) for _ in range(M)] 
dp[N] = 1

for i in range(N-1, -1, -1):
    if (i in A) == False:
        dp[i] = dp[i + 1] + dp[i + 2] 

print(dp[0] % mod)


### FIXED CODE ###

N, M = map(int, input().split())
mod = 1000000007
dp = [0] * (N+2)
A = set([int(input()) for _ in range(M)]) 
dp[-2] = 1

for i in range(N-1, -1, -1):
    if (i in A) == False:
        dp[i] = (dp[i + 1] + dp[i + 2]) % mod 

print(dp[0])
### BUGGY CODE ###

from collections import deque
h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())

maze = [list(input()) for i in range(h)]
ans = [[-1]*w for i in range(h)]

dx=[0,1,0,-1]
dy=[1,0,-1,0]

ans[ch-1][cw-1]=0
def bfs(ans):
  qu = deque([])
  qu.append([cw-1,ch-1])
  while qu:
    zahyou=qu.popleft()
    x=zahyou[0]
    y=zahyou[1]
    for i in range(4):
      if 0 <= x+dx[i] < w and 0 <= y+dy[i] < h:
        if maze[y+dy[i]][x+dx[i]]=="." and (ans[y+dy[i]][x+dx[i]]>ans[y][x] or ans[y+dy[i]][x+dx[i]]==-1):
          qu.append([x+dx[i],y+dy[i]])
          ans[y+dy[i]][x+dx[i]] = ans[y][x]
    for i in range(x-2,x+3):
      for j in range(y-2,y+3):
        if 0<=i<w and 0<=j<h:
          if maze[j][i]=="." and (ans[j][i]>ans[y][x]+1 or ans[j][i]==-1):
            ans[j][i]=(ans[y][x]+1)
            qu.append([i,j])

bfs(ans)
print(ans[dh-1][dw-1])
  

### FIXED CODE ###

from collections import deque
h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())

maze = [list(input()) for i in range(h)]
ans = [[-1]*w for i in range(h)]

dx=[0,1,0,-1]
dy=[1,0,-1,0]

ans[ch-1][cw-1]=0
def bfs(ans):
  qu = deque([])
  qu.append([cw-1,ch-1])
  while qu:
    zahyou=qu.popleft()
    x=zahyou[0]
    y=zahyou[1]
    count=0
    for i in range(4):
      if 0 <= x+dx[i] < w and 0 <= y+dy[i] < h:
        if maze[y+dy[i]][x+dx[i]]=="." and (ans[y+dy[i]][x+dx[i]]>ans[y][x] or ans[y+dy[i]][x+dx[i]]==-1):
          qu.appendleft([x+dx[i],y+dy[i]])
          ans[y+dy[i]][x+dx[i]] = ans[y][x]
          count+=1
    if count!=4:
      for i in range(x-2,x+3):
        for j in range(y-2,y+3):
          if 0<=i<w and 0<=j<h:
            if maze[j][i]=="." and (ans[j][i]>ans[y][x]+1 or ans[j][i]==-1):
              ans[j][i]=(ans[y][x]+1)
              qu.append([i,j])

bfs(ans)
print(ans[dh-1][dw-1])
### BUGGY CODE ###

import math

n, m = map(int, input().split())
A = list(map(int, input().split()))
As = sorted(A, reverse = True)
for i in range(m):
    ii = math.floor(As[0]/2)
    As[0] = ii
    if len(As) > 1:
        if As[0] < As[1]:
            As = sorted(As, reverse=True)


print(int(sum(As)))


### FIXED CODE ###

import math
import heapq

n, m = map(int, input().split())
A = list(map(int, input().split()))
A = list(map(lambda x:x*(-1), A))
heapq.heapify(A)
for i in range(m):
    min = (-1)*((-1)*(heapq.heappop(A))//2)
    heapq.heappush(A, min)


print(int(sum(A))*(-1))
### BUGGY CODE ###

def c_many_medians(N, X):
    x = [[0, 0] for _ in range(N)]
    for i, e in enumerate(X):
        x[i] = [i, e]
    x.sort(key=lambda k: k[1])
    mid = N // 2 - 1
    a, b = [0] * N, [0] * N
    for i, (k, v) in enumerate(x):
        p=x.index([k,v])
        a[k] = p
        b[i] = v
    ans = ['' for _ in range(N)]
    for i in a:
        if b[mid]>=b[a[i]]:
            ans[i]='{}'.format(b[mid+1])
        else:
            ans[i]='{}'.format(b[mid])
    return '\n'.join(ans)

N = int(input())
X = [int(i) for i in input().split()]
print(c_many_medians(N, X))

### FIXED CODE ###

def c_many_medians(N, X):
    # 解説どおり
    Y = sorted(X)
    ans = ['' for _ in range(N)]
    pos = N // 2
    for k, xi in enumerate(X):
        if xi < Y[pos]:
            ans[k] = str(Y[pos])
        else:
            ans[k] = str(Y[pos - 1])
    return '\n'.join(ans)

N = int(input())
X = [int(i) for i in input().split()]
print(c_many_medians(N, X))
### BUGGY CODE ###

import sys
a = input()
cnt = 0
while True:
    c = a.count("BW")
    a = a.replace("BW","WB")
    if c != 0:
        cnt += c
    else:
        print(cnt)
        sys.exit(0)

### FIXED CODE ###

import sys
a = [ c for c in input()]
B = 0
W = 0
for i in range(len(a)):
    if a[i] == "B":
        B += 1
    else:
        W += B

print(W)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, M = [int(item) for item in input().split()]
A = [int(item) for item in input().split()]

for i in range(M):
    b, c = [int(item) for item in input().split()]
    A.extend([c]*b)

A.sort()
print(sum(A[-N:]))


### FIXED CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline

N, M = [int(item) for item in input().split()]
A = [int(item) for item in input().split()]
A.sort()

new_dict = defaultdict(lambda: 0)
for i in range(M):
    b, c = [int(item) for item in input().split()]
    new_dict[c] += b
new_dict = sorted(new_dict.items(), key=lambda x: -x[0])

new_list = []
for k, v in new_dict:
    if v > N:
        v = N
    new_list += [k] * v
    if len(new_list) >= N:
        break

new_list = new_list[:N]

#####

n = min(N, len(new_list))
for i in range(n):
    if A[i] >= new_list[i]:
        break
    A[i] = new_list[i]

print(sum(A))
### BUGGY CODE ###

#import numpy as np

N = int(input())
A = list(map(int, input().split()))
A.sort()#わるほう

kouho = sorted([x for x in set(A) if A.count(x) == 1])
#maxA = 10**5

#target = kouho[:]
maxA = A[-1]
work=[0]*(A[-1]+1)

for i in range(len(A)):
    maxN = int(maxA/A[i])
    for n in range(1,maxN+1):
        buf = A[i]*n
        #remove_list.append(buf)
        work[buf]+=1
            #print(A[i]*n)
#target = kouho[:]
#kouho = list(set(kouho) - set(remove_list))

sm=0
for s in A:
    if work[s]==1: sm+=1
print(sm)

#print(len(kouho))

### FIXED CODE ###

#import numpy as np

N = int(input())
A = list(map(int, input().split()))
A.sort()#わるほう

#kouho = sorted([x for x in set(A) if A.count(x) == 1])
#maxA = 10**5

#target = kouho[:]
maxA = A[-1]
work=[0]*(A[-1]+1)

for i in range(len(A)):
    if work[A[i]]<=1:
        maxN = int(maxA/A[i])
        for n in range(1,maxN+1):
            buf = A[i]*n
            #remove_list.append(buf)
            work[buf]+=1
                #print(A[i]*n)

#target = kouho[:]
#kouho = list(set(kouho) - set(remove_list))

sm=0
for s in A:
    if work[s]==1: sm+=1
print(sm)

#print(len(kouho))
### BUGGY CODE ###

"""
dp[i][j][k] => i行目j列到達時点での最大価値。i行目において拾えるアイテムの数はK個。
"""
R,C,K = map(int,input().split())
items = [[0]*C for _ in range(R)]
for _ in range(K):
    r,c,v = map(int,input().split())
    items[r-1][c-1] = v

dp = [[[0]*4 for _ in range(C)]for _ in range(R)]

for i in range(R):
    for j in range(C):
        v = items[i][j]

        #上から入るパターン
        dp[i][j][0] = max(dp[i-1][j])
        if v:
            dp[i][j][1] = dp[i][j][0]+v
        
        #左から入ってくるパターン
        if j > 0:
            for k in range(4):
                #このマスのアイテムをとらないパターン
                dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k])
                if v and k>0:
                    dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k-1]+v)

print(max(dp[-1][-1]))

### FIXED CODE ###

"""
dp[i][j]　=> i行目j列目がゴールの場合の最大値
"""
def main():
    import sys
    input = sys.stdin.readline
    R,C,K = map(int,input().split())
    items = [[0]*(C) for _ in range(R)]

    for _ in range(K):
        r,c,v = map(int,input().split())
        items[r-1][c-1] = v

    dp = [[0]*4 for _ in range(C)]
    dp[0][1] = items[0][0]
    for i in range(R):
        for j in range(C):
            v = items[i][j]
            if i==0 and j == 0:
                continue

            if i!=0:
                #上から入る場合のシミュレート
                dp[j][0] = max(dp[j])
                if v:
                    dp[j][1] = dp[j][0]+v

            if j!=0:
                #左から入る場合のシミュレート
                dp[j][0] = max(dp[j][0],dp[j-1][0])
                if v:
                    #itemが存在する場合の処理
                    for k in range(1,4):
                        dp[j][k] = max(dp[j][k],dp[j-1][k-1]+v,dp[j-1][k])
                else:
                    for k in range(1,4):
                        dp[j][k] = max(dp[j][k],dp[j-1][k])
    print(max(dp[-1]))
main()
### BUGGY CODE ###

num = int(input())
dic = [input() for i in range(num)]

sdic = []
ans = 0
for i in range(num):
    sdic.append("".join(sorted(dic[i])))
for i in range(num):
    ans += (sdic.count(sdic[0]) - 1)
    sdic.pop(0)
print(ans)

### FIXED CODE ###

num = int(input())
li = [input() for i in range(num)]

dic = {}
ans = 0
for i in range(num):
    now = "".join(sorted(li[i]))
    if now in dic:
        dic[now] += 1
    else:
        dic[now] = 1
for i in dic:
    n = dic[i]
    ans += int((n*(n-1))/2)

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

h,w=map(int,input().split())
field=[list(input())for i in range(h)]

import copy
dp=[[1000 for i in range(w)]for i in range(h)]
for y,i in enumerate(field):
    for x,j in enumerate(i):
        if j=="#":
            dp[y][x]=9999

dydx=[[-1,0],[1,0],[0,-1],[0,1]]

maxi=0
for y,i in enumerate(field):
    for x,j in enumerate(i):
        if j==".":
            ndp=copy.deepcopy(dp)
            ndp[y][x]=0
            
            for _ in range(280):
                for y,i in enumerate(ndp):
                    for x,j in enumerate(i):
                        if j<1000:
                            for dy,dx in dydx:
                                ny,nx=y+dy,x+dx
                                if 0<=ny<=h-1 and 0<=nx<=w-1 and field[ny][nx]!="#" and ndp[ny][nx]>ndp[y][x]:
                                    ndp[ny][nx]=ndp[y][x]+1
            for y,i in enumerate(ndp):
                for x,j in enumerate(i):
                    if j==9999:
                        ndp[y][x]=0
                        continue
                    if j>maxi:
                        maxi=j
print(maxi)

### FIXED CODE ###

h,w=map(int,input().split())
field=[list(input())for i in range(h)]

import copy
dp=[[1000 for i in range(w)]for i in range(h)]
for y,i in enumerate(field):
    for x,j in enumerate(i):
        if j=="#":
            dp[y][x]=9999

dydx=[[-1,0],[1,0],[0,-1],[0,1]]
#print(dp)
maxi=0
for y,i in enumerate(field):
    for x,j in enumerate(i):
        if j==".":
            ndp=copy.deepcopy(dp)
            ndp[y][x]=0
            cnt=0
            queue=[]
            queue.append([y,x])
            while queue:
                ny,nx=queue.pop(0)
                for dy,dx in dydx:
                    nny,nnx=ny+dy,nx+dx
                    if 0<=nny<=h-1 and 0<=nnx<=w-1 and field[nny][nnx]!="#" and ndp[nny][nnx]==1000:
                        ndp[nny][nnx]=ndp[ny][nx]+1
                        queue.append([nny,nnx])
                        if ndp[nny][nnx]>maxi:
                            maxi=ndp[nny][nnx]
            #print(ndp)
print(maxi)
### BUGGY CODE ###

S = int(input())
x1, y1 = 0, 0
y2 = 0
x3 = 0
x2, y3 = 0, 0

for i in range(int(S ** 0.5), S + 1):
  x2 = i
  y3 = S // i
  if S % x2 == 0 and x2 <= 1000000000 and y3 <= 1000000000:
    break
print("{} {} {} {} {} {}".format(x1, y1, x2, y2, x3, y3))

### FIXED CODE ###

S = int(input())
MOD = 10 ** 9
x1, y1, x2, y2 = 0, 0, MOD, 1
y3 = S // MOD
if S % MOD != 0:
  y3 += 1
x3 = x2 * y3 - S

print("{} {} {} {} {} {}".format(x1, y1, x2, y2, x3, y3))
### BUGGY CODE ###

X, Y = input().split()
X = int(X)
Y = int(Y)

if Y % 2 == 1:
    print('No')
elif X * 4 < Y:
    print('No')
else:
    count = 0
    while True:
        Y = Y / 2
        count += 1
        if Y == 1:
            break
    if 2 * X >= count:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

"""
2 * a + 4 * 2 * (X - a) = Y
2a + 8X - 8a = Y
8X - 6a = Y


2 * turu + 4 * kame = Y
turu + kame = X
turu = X - kame

2(X - kame) + 4kame = Y
2X - 2kame + 4kame = Y
2X + 2kame = Y
2kame = Y - 2X
kame = (Y - 2X) / 2
"""


X, Y = input().split()
X = int(X)
Y = int(Y)

a = (Y - 2 * X) / 2

if a >= 0 and X >= a and a == int(a):
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

#A
n = int(input())
a = list(map(int, input().split()))
ans = 1
b = 0
for i in a:
    ans *= i
    if ans > 10 ** 18:
        b = -1
if ans == 0:#例外ans=0のときは途中で10^18を超えても0となる
    b = 0
if b == -1:#10^18を超えてる
    print(-1)
else:
    print(ans)


### FIXED CODE ###

#B
n=int(input())
a = list(map(int, input().split()))
a.sort()
ans=1
for i in a:
    ans *= i
    if ans == 0:
        break
    if ans > 10 ** 18:
        ans = -1
        break
print(ans)
### BUGGY CODE ###

a, b, c = map(int, input().split())
while c:
  if c > a:
    c -= a
    a = 0
    b -= c
  else:
    a -= c
    c = 0
print(a, b)

### FIXED CODE ###

a, b, c = map(int, input().split())
if c > a:
	c -= a
	a = 0
	b = max(0, b-c)
else:
	a -= c
print(a, b)
### BUGGY CODE ###

import bisect

def main():
    N, M, K = map(int, input().split())
    A = [int(v) for v in input().split()]
    B = [int(v) for v in input().split()]
    if N < M:
        for _ in range(M-N):
            A.append(0)
    else:
        for _ in range(N-M):
            B.append(0)
    C = [v1+v2 for v1, v2 in zip(A, B)]
    ruisekiA = [0 for _ in range(len(C)+1)]
    ruisekiB = [0 for _ in range(len(C)+1)]
    ruisekiC = [0 for _ in range(len(C)+1)]
    for i in range(len(C)):
        ruisekiA[i + 1] = ruisekiA[i] + A[i]
        ruisekiB[i + 1] = ruisekiB[i] + B[i]
        ruisekiC[i + 1] = ruisekiC[i] + C[i]

    ans = 0
    # i番目までは両方読む
    for i in range(min(N, M)+1):
        tans = i * 2
        tk = K - ruisekiC[i]
        if tk < 0:
            continue

        # A だけ、Bだけで何冊読めるか考える
        idx_a = bisect.bisect_left(ruisekiA[:N+1], tk + ruisekiA[i])
        if idx_a == len(ruisekiA) or ruisekiA[idx_a] != tk + ruisekiA[i]:
            idx_a -= 1
        idx_b = bisect.bisect_left(ruisekiB[:M+1], tk + ruisekiB[i])
        if idx_b == len(ruisekiB) or ruisekiB[idx_b] != tk + ruisekiB[i]:
            idx_b -= 1
        ans = max(ans, max(tans+idx_a-i, tans+idx_b-i))
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import bisect


def main():
    N, M, K = map(int, input().split())
    A = [int(v) for v in input().split()]
    B = [int(v) for v in input().split()]
    ruisekiA = [0 for _ in range(N+1)]
    ruisekiB = [0 for _ in range(M+1)]
    for i in range(N):
        ruisekiA[i + 1] = ruisekiA[i] + A[i]
    for i in range(M):
        ruisekiB[i + 1] = ruisekiB[i] + B[i]

    ans = 0
    # A を i 個 使う
    for i in range(N+1):
        tans = i
        tk = K - ruisekiA[i]
        if tk < 0:
            break
        idx = bisect.bisect_left(ruisekiB, tk)
        if M+1 == idx or ruisekiB[idx] != tk:
            idx -= 1
        tans += idx
        ans = max(ans, tans)
    print(ans)


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

import copy
from itertools import product, combinations

N = int(input())

dp = []
for _ in range(N):
    dp.append(list(map(int, input().split(' '))))

original = copy.deepcopy(dp)

for k, i, j in product(range(N), repeat=3):
    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

if dp == original:
    cost = 0
    for i in range(N):
        for j in range(i + 1, N):
            for k in range(N):
                if k == i or k == j:
                    continue
                if dp[i][j] == dp[i][k] + dp[k][j]:
                    break
            else:
                cost += dp[i][j]
    print(cost)
else:
    print(-1)


### FIXED CODE ###

import copy
from itertools import product, combinations

N = int(input())

dp = []
for _ in range(N):
    dp.append(list(map(int, input().split(' '))))

original = copy.deepcopy(dp)

for k, i, j in product(range(N), repeat=3):
    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

if dp == original:
    cost = 0
    for i in range(N):
        for j in range(i + 1, N):
            for k in range(N):
                if k == i or k == j:
                    continue
                if dp[i][j] == dp[i][k] + dp[k][j]:
                    break
            else:
                cost += dp[i][j]
    print(cost)
else:
    print(-1)
### BUGGY CODE ###

n = int(input())
s = input()
cou = 0
for i in range(1000):
  i = "{0:03d}".format(i)
  t = 0
  r = 0
  while r!=n:
    if s[r]==i[t]:
      t += 1
    if t==3:
      cou += 1
      r = n-1
    r += 1            
print(cou)

### FIXED CODE ###

n = int(input())
s = input()
cou = 0
for i in range(1000):
  i = "{0:03d}".format(i)
  t = 0
  r = 0
  while r!=n:
    if s[r]==i[t]:
      t += 1
    if t==3:
      cou += 1
      r = n-1
    r += 1            
print(cou)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
 
n = int(input())
ab = [list(map(int, input().split())) for _ in range(n-1)]
 
graph = [[] for _ in range(n)]
 
for a, b in ab:
    graph[a-1].append((b-1, -1))
    graph[b-1].append((a-1, -1))
 
# print(graph)
 
stack = [(0, -1)]
visited = [-1]*n
 
k = 0
while stack:
    node, color = stack.pop()
    visited[node] = 1
 
    if k < len(graph[node]):
        k = len(graph[node])
    tmp = 1
    for i, (child, child_color) in enumerate(graph[node]):
        if visited[child] == 1:
 
            continue
        if child_color == -1:
            if tmp == color:
                tmp += 1
            graph[node][i] = (child, tmp)
            stack.append((child, tmp))
            tmp +=1
 
print(k)
for a, b in ab:
   for node, color in graph[a-1]:
       if node == b-1:
           print(color) 
           

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import deque
 
n = int(input())
ab = [list(map(int, input().split())) for _ in range(n-1)]
 
graph = [[] for _ in range(n)]
for a, b in ab:
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

stack = deque([0])
parent = [None]*n
colors = [0]*n
while stack:
    node = stack.popleft()
    color = 1
    for child in graph[node]:
        if child == parent[node]:
            continue
        parent[child] = node
        if color == colors[node]:
            color += 1
        colors[child] = color
        color += 1
        stack.append(child)

 
k = max(colors)
print(k)
for a, b in ab:
    if (a-1) == parent[b-1]:
        print(colors[b-1])
    else:
        print(colors[a-1])
### BUGGY CODE ###

import sys
s= sys.stdin.readline().rstrip() 
t= sys.stdin.readline() .rstrip()
Ns=len(s)
Nt=len(t)
i=1
dp=[["" for i in range(Nt+1)]for j in range(Ns+1)]
while i<=Ns:
    j=1
    while j<=Nt:
        if s[i-1]==t[j-1]:
            dp[i][j]=dp[i-1][j-1]+s[i-1]
        else:
            if len(dp[i][j-1])>len(dp[i-1][j]):
                dp[i][j]=dp[i][j-1]
            else:
                dp[i][j]=dp[i-1][j]
        j+=1
    i+=1
print(dp[Ns][Nt])

### FIXED CODE ###

S=input()
T=input()
dp=[[0 for j in range(len(T)+1)] for i in range(len(S)+1)]
for i in range(len(S)):
    for j in range(len(T)):
        if S[i]==T[j]:
            dp[i+1][j+1]=dp[i][j]+1
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i+1][j])
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j+1])
i=len(S)
j=len(T)
ans=""
while i>0 and j>0:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans=S[i-1]+ans
        i-=1
        j-=1
print(ans)
### BUGGY CODE ###

s = input()
mods = [0]*2019
mods[0] = 1
accu = 0
for i, j in enumerate(reversed(s)):
    accu += int(j)*10**i
    accu %= 2019
    mods[accu] += 1
ans = 0
for i in mods:
    ans += i*(i-1)//2
print(ans)

### FIXED CODE ###

s = input()
mods = [0]*2019
mods[0] = 1
accu = 0
for i, j in enumerate(reversed(s)):
    accu += int(j)*pow(10, i, 2019)
    accu %= 2019
    mods[accu] += 1
ans = 0
for i in mods:
    ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def frog_2():
    N, K = map(int,input().split())
    h = tuple(map(int,input().split()))

    dp = [float("inf")] * (N)
    dp[0] = 0

    for n in range(1, N):
        k = max(0, n - K)
        dp[n] = min(abs(h[n] - h[i]) + dp[i] for i in range(k, n))
        
    return print(dp[-1])

frog_2()

### FIXED CODE ###

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

dp = [float('inf') for _ in range(n)]
dp[0] = 0

for i in range(n-1):
    for j in range(1, k+1):
        if i+j <= n-1:
            temp = dp[i] + abs(l[i+j] - l[i])
            if temp < dp[i+j]:
                dp[i+j] = temp

print(dp[-1])
### BUGGY CODE ###

n = input()
a = list(map(int,input().split()))
sum = 1
for i in a:
    sum*=i

if sum > 10**18:
    print(-1)
else:
    print(sum)

### FIXED CODE ###

n = input()
a = list(map(int,input().split()))
pro = 1
if 0 in a:
    print(0)
else:
    for i in a:
        pro*=i
        if pro > 10**18:
            pro = -1
            break
    print(pro)
### BUGGY CODE ###

k,s=map(int,input().split())
count=0

if k*3==s:
  print(1)
  exit()

for x in range(k+1):
  for y in range(k+1):
    for z in range(k+1):
      if x+y+z==s:
        count+=1
print(count)

### FIXED CODE ###

k,s=map(int,input().split())
count=0

if k*3==s:
  print(1)
  exit()

for x in range(k+1):
  for y in range(k+1):
    z=s-x-y
    if z>=0 and z<=k:
      count+=1
print(count)
### BUGGY CODE ###

N,M=map(int,input().split())
yen=[]
hon=[]
for i in range(N):
    a,b=map(int,input().split())
    yen.append(a)
    hon.append(b)

loop=True
pay=0

while loop:
    mise=yen.index(min(yen))
    value=yen[mise]
    stock=hon[mise]
    if M>stock:
        pay+=stock*value
    else:
        pay+=M*value
    M-=stock
    del yen[mise]
    del hon[mise]

    if M<=0:
        loop=False

print(pay)

### FIXED CODE ###

N,M=map(int,input().split())
mises=[]
for i in range(N):
    mises.append(list(map(int,input().split())))

mises.sort()
pay=0
for i in mises:
    if i[1]<M:
        pay+=i[0]*i[1]
        M-=i[1]
    else:
        pay+=i[0]*M
        break
print(pay)
### BUGGY CODE ###

input()
a = list(map(int, input().split()))
ans = 1
for el in a:
    ans *= el
if ans > 1e18:
    print(-1)
else:
    print(ans)



### FIXED CODE ###

def main():
    input()
    a = list(map(int, input().split()))
    ans = 1
    for el in a:
        if el == 0:
            print(0)
            return
    for el in a:
        ans *= el
        if ans > 1e18:
            print(-1)
            return
    else:
        print(ans)


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

import re
N,Q = map(int, input().split())
S = input()
for i in range(Q):
  l,r = map(int, input().split())
  print(len(re.findall('AC', S[l-1:r])))

### FIXED CODE ###

#!/usr/bin/env python3
import sys

def main():
    N, Q = map(int, input().split())
    S = input()
    ans = [None] * N
    ans[0] = S.count('AC')
    for i in range(1,N):
        ans[i] = ans[i-1]
        if S[i-1:i+1] == 'AC':
            ans[i] -= 1

    for i in range(Q):
        l, r = map(int, input().split())
        print(ans[l-1] - ans[r-1])

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

n,k = map(int,input().split())
l = list(map(int,input().split()))
dp = [float("inf")]*(n+1)
for i in range(n):
  if i ==0:
    dp[0]=0
  for j in range(1,k+1):
    if i-j>=0:
    	dp[i]=min(dp[i],dp[i-j]+abs(l[i]-l[i-j]))
print(dp[n-1])

### FIXED CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
min_cost=[0]*n
min_cost[0]=0
min_cost[1]=abs(h[1]-h[0])
for i in range(2,n):
    s=[]
    for j in range(1,k+1):
        if i-j<0:
            continue
        s.append(min_cost[i-j]+abs(h[i]-h[i-j]))
    min_cost[i]=min(s)
print(min_cost[-1])