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

n, k = map(int, input().split())
h = list(map(int, input().split()))
INF = 10 ** 18

dp = [INF] * n
dp[0] = 0

for i, ei in enumerate(h):
    for j in range(i - 1, max(0, i - k) - 1, -1):
        ej = h[j]
        dp[i] = min(dp[i], dp[j] + abs(ei - ej))

ans = dp[-1]
print(ans)


### FIXED CODE ###

import numpy as np

n, k = map(int, input().split())
h = np.array(list(map(int, input().split())), np.int64)
INF = 10 ** 18

dp = np.full(n, INF, np.int64)
dp[0] = 0

for i, e in enumerate(h[1:], 1):
    lb = max(0, i - k)
    dp[i] = np.min(dp[lb:i] + np.abs(h[lb:i] - e))

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

#<D>
import itertools
N = int(input())
num = [n for n in range(1, N + 1)]
print(list(itertools.accumulate(num))[N - 1] - N)
    


### FIXED CODE ###

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

import sys
input = sys.stdin.readline
N,M = map(int, input().split())
A = list(map(int, input().split()))

for i in range(M):
  index = A.index(max(A))
  A[index] = A[index]//2

print(sum(A))


### FIXED CODE ###

import sys
from heapq import heappush, heappop
input = sys.stdin.readline
N,M = map(int, input().split())
A = []
for a in input().split():
  heappush(A,-int(a))

for _ in range(M):
  tmp = heappop(A)
  heappush(A, -(-tmp//2))

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

N, Q = map(int, input().split())
S = input()
l = 0
r = 0
for i in range(Q):
    l, r = map(int, input().split())
    print(S[l-1: r].count("AC"))

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
a=[0]*n
for i in range(n):
    if i:
        a[i]=a[i-1]+(s[i-1:i+1]=='AC')
for _ in range(q):
    l,r=map(int,input().split())
    print(a[r-1]-a[l-1])
### BUGGY CODE ###

import math

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

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

x = max(a)
maxc = 0
maxy = 0
for y in sorted(a):
    if x == y or y < x // 2:
        continue
    c = comb(x, y)
    if maxc < c:
        maxc = c
        maxy = y

print(str(x) + ' ' + str(maxy))


### FIXED CODE ###

import math

n = int(input())
a = [int(x) for x in input().split()]
a.sort()
x = max(a)
a.remove(x)
maxi = 0
mind = x
for i in range(len(a)):
    d = abs((x+1) // 2 - a[i])
    if d < mind:
        maxi = i
        mind = d
print(str(x) + ' ' + str(a[maxi]))
### BUGGY CODE ###

#!/usr/bin/env python3
# Atcoder necoak answer
# https://atcoder.jp/contests/diverta2019/tasks/diverta2019_a
import itertools

intext = input()
[n, k] = map(int, intext.split())

int_list = [v for v in range(1, n+1)]
nk_combis = itertools.combinations(int_list, k)
ans_nk_combis = []

for nk_combi in nk_combis:
    # print(nk_combi) #
    nk_list = list(nk_combi)
    nk_list.sort()

    prev_item = None
    is_renzoku = True

    for nk_item in nk_list:
        # print(prev_item, nk_item)
        if prev_item == None:
            prev_item = nk_item
            continue
        if prev_item + 1 != nk_item:
            is_renzoku = False
            break
        prev_item = nk_item

    if is_renzoku:
        ans_nk_combis.append(nk_list)

# print(ans_nk_combis)
print(len(ans_nk_combis))


### FIXED CODE ###

#!/usr/bin/env python3
# Atcoder necoak answer
# https://atcoder.jp/contests/diverta2019/tasks/diverta2019_a
import itertools

intext = input()
[n, k] = map(int, intext.split())
print(n-k+1)
### BUGGY CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
BC=[list(map(int,input().split())) for _ in range(M)]

dic=dict({})
for i in range(N):
    if A[i] not in dic.keys():
        dic[A[i]]=1
    else:
        dic[A[i]]+=1

for i in range(M):
    if BC[i][1] not in dic.keys():
        dic[BC[i][1]]=BC[i][0]
    else:
        dic[BC[i][1]]+=BC[i][0]

dic = sorted(dic.items(), reverse=True)
cnt=0
ans=0
for i in range(len(dic)):
    if cnt>=N:
        break
    else:
        if cnt+dic[i][1]<=N:
            cnt+=dic[i][1]
            ans+=dic[i][0]*dic[i][1]
        else:
            ans+=dic[i][0]*(N-cnt)
            break
print(ans)

### FIXED CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
BC=[list(map(int,input().split())) for _ in range(M)]

dic=dict({})
for i in range(N):
    if A[i] not in dic.keys():
        dic[A[i]]=1
    else:
        dic[A[i]]+=1

for i in range(M):
    if BC[i][1] not in dic.keys():
        dic[BC[i][1]]=BC[i][0]
    else:
        dic[BC[i][1]]+=BC[i][0]

dic = sorted(dic.items(), reverse=True)
cnt=0
ans=0
for i in range(len(dic)):
    if cnt>=N:
        break
    else:
        if cnt+dic[i][1]<=N:
            cnt+=dic[i][1]
            ans+=dic[i][0]*dic[i][1]
        else:
            ans+=dic[i][0]*(N-cnt)
            break
print(ans)
### BUGGY CODE ###

import math
N=int(input())
for n in range(1,N+1):
  tmp=0
  for x in range(1,100):
    for y in range(1,100):
      if 4*n-3*x**2-2*x*y-3*y**2<0:continue
      z=0.5*(math.sqrt(4*n-3*x**2-2*x*y-3*y**2)-x-y)
      if z.is_integer() and z>=1:
        tmp+=1
      z=0.5*(math.sqrt(4*n-3*x**2-2*x*y-3*y**2)*(-1)-x-y)
      if z.is_integer() and z>=1:
        tmp+=1
  print(tmp)

### FIXED CODE ###

import math
N=int(input())
for n in range(1,N+1):
  tmp=0
  for x in range(1,100):
    for y in range(1,100):
      if 4*n-3*x**2-2*x*y-3*y**2<0:continue
      z=0.5*(math.sqrt(4*n-3*x**2-2*x*y-3*y**2)-x-y)
      if z.is_integer() and z>=1:
        tmp+=1
      z=0.5*(math.sqrt(4*n-3*x**2-2*x*y-3*y**2)*(-1)-x-y)
      if z.is_integer() and z>=1:
        tmp+=1
  print(tmp)
### BUGGY CODE ###

from collections import deque
n=int(input())
s=deque([])
cnt=0
for _ in range(n):
    s.append(''.join(sorted(input())))
for i in range(n):
    for j in range(n):
        if i<j:
            if s[i]==s[j]:
                cnt+=1
print(cnt)

### FIXED CODE ###

n=int(input())
L=[[] for _ in range(n)]
ans=0
for i in range(n):
    L[i]=sorted(list(input()))
L=sorted(L)
tmp=1
ans=0
for i in range(n-1):
    if L[i]==L[i+1]:
        tmp+=1
    else:
        ans+=tmp*(tmp-1)//2
        tmp=1
ans+=tmp*(tmp-1)//2
print(ans)
### BUGGY CODE ###

n = int(input())
s = list(input() for _ in range(n))

l = list(set(s))

count = [0] * len(l)
for i, v in enumerate(l):
    count[i] = s.count(v)

m = max(count)
indexes = [i for i, x in enumerate(count) if x == m]

ans = []
for i in indexes:
    ans.append(l[i])

ans.sort()

for i in ans:
    print(i)

### FIXED CODE ###

import collections

n = int(input())
s = list(input() for _ in range(n))

c = dict(collections.Counter(s))
m = max(c.values())
ans = [k for k, v in c.items() if v == m]

ans.sort()
for i in ans:
    print(i)
### BUGGY CODE ###

def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(int(n))
  return table
def main():
  sFlag=False
  X= int(input())
  X_table=prime_decomposition(X)
  X_table.append(1)
  for i in range(X):
    A=i
    for j in range(len(X_table)):
      B=A-X_table[j]
      X_n=A**5-B**5
      if(X_n==X):
        print(A,B)
        sFlag=True
        break
    if(sFlag==True):
      break

if __name__=='__main__':
  main()

### FIXED CODE ###

def main():
  sFlag=False
  X= int(input())
  for i in range(-1000,1000):
    for j in range(-1000,1000):
      X_n=i**5-j**5
      if(X_n==X):
        print(i,j)
        sFlag=True
        break
    if(sFlag==True):
      break
 
if __name__=='__main__':
  main()
### BUGGY CODE ###

n = int(input())

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

i=0
list = []

for a_s in a:
    length = len(a)
    x = a.index((length) - i) + 1
    list.insert(0, x)
    i += 1

print(*list)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split(" ")))
dic = {}
i = 0
for a_s in a:
    dic.setdefault(i, a_s)
    i += 1
for k, v in sorted(dic.items(), key=lambda x: x[1]):
    print(k + 1)
### BUGGY CODE ###

import numpy as np

import sys

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

towngroup = np.array(list(range(N)))

howmuch = np.array([[10**9+1]*N for i in range(N)])

for i in range(N):
    for j in range(i, N):
        howmuch[i][j] = min(abs(x[i] - x[j]), abs(y[i] - y[j]))

cheapbridge = np.argsort(howmuch.flatten())

cost = 0

for i in cheapbridge[:]:
    a = i // N
    b = i % N
    if towngroup[a] == towngroup[b]:
        continue

    cost += min(abs(x[a] - x[b]), abs(y[a] - y[b]))

    towngroup[towngroup == towngroup[b]] = towngroup[a]

    if len(set(towngroup)) == 1:
        print(cost)
        sys.exit()


### FIXED CODE ###

import sys

import numpy as np


class Graph:
    def __init__(self, N):
        self.townarrow = [i for i in range(N)]

    def find(self, x):
        if x == self.townarrow[x]:
            return x
        else:
            self.townarrow[x] = self.find(self.townarrow[x])
            return self.townarrow[x]

    def union(self, x, y):
        self.link(self.find(x), self.find(y))

    def link(self, x, y):
        self.townarrow[y] = x


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

useful_road = []

l = sorted(range(N), key=lambda j: x[j])
for i in range(len(l) - 1):
    cost = min(abs(x[l[i]] - x[l[i + 1]]), abs(y[l[i]] - y[l[i + 1]]))
    useful_road.append((cost, l[i], l[i + 1]))

l = sorted(range(N), key=lambda j: y[j])
for i in range(len(l) - 1):
    cost = min(abs(x[l[i]] - x[l[i + 1]]), abs(y[l[i]] - y[l[i + 1]]))
    useful_road.append((cost, l[i], l[i + 1]))


m = 0
cost = 0
towngroup = Graph(N)
for c, i, j in sorted(useful_road):
    if towngroup.find(i) == towngroup.find(j):
        continue
    cost += c
    m += 1

    towngroup.union(i, j)

    if m == N - 1:
        print(cost)
        sys.exit()
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from itertools import product

n, m, q = map(int, readline().split())
abcd = [list(map(int, readline().split())) for _ in range(q)]
ans = 0
for bit in product([0, 1], repeat=q):
    cnt = 0
    aaa = []
    aaaa = []
    for i, (a, b, c, d) in enumerate(abcd):
        if bit[i] == 1:
            aaa.append([a, b, c])
    for a, b, c in aaa[::-1]:
        for aa, bb, cc in aaa:
            if aa == a and b < bb:
                aaaa.append([b, bb, cc - c])
            elif aa == a and b > bb:
                aaaa.append([bb, b, c - cc])
            if b == bb and aa > a:
                aaaa.append([a, aa, cc - c])
            elif b == bb and aa < a:
                aaaa.append([aa, a, c - cc])
    aaa += aaaa
    flag = True
    for i, (a, b, c, d) in enumerate(abcd):
        if bit[i] == 1:
            for aa, bb, cc in aaa:
                if (aa <= a < b <= bb and c > cc) or (a <= aa < bb <= b and c < cc):
                    if aa == a and bb == b and c == cc:
                        continue
                    else:
                        flag = False
                        break
            if flag:
                cnt += d
            else:
                break
    if ans < cnt:
        ans = cnt
print(ans)


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from itertools import combinations_with_replacement

n, m, q = map(int, readline().split())
abcd = [list(map(int, readline().split())) for _ in range(q)]
ans = 0
for seq in combinations_with_replacement(range(m), n):
    cnt = 0
    for a, b, c, d in abcd:
        if seq[b - 1] - seq[a - 1] == c:
            cnt += d
    ans = max(ans, cnt)
print(ans)
### BUGGY CODE ###

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

if d == 0:
    x = n
    if n == 1:
        result = m - 1
    else:
        result = x*(m-1)*n**(m-2)/n**m


else:
    x = 2*(n - d)

    result = x*(m-1)*n**(m-2)/n**m

print(result)

### FIXED CODE ###

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

if d == 0:
    x = n
    if n == 1:
        result = m - 1
    else:
        result = x*(m-1)/n**2


else:
    x = 2*(n - d)

    result = x*(m-1)/n**2

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

import sys

input = sys.stdin.readline


def main():
    N, M = [int(x) for x in input().split()]
    A = []
    C = []
    for _ in range(M):
        a, b = [int(x) for x in input().split()]
        A.append(a)
        c = [int(x) for x in input().split()]
        tmp = 0
        for cc in c:
            tmp |= 1 << (cc - 1)

        C.append(tmp)

    dp = [float("inf")] * (2 ** N + 1)

    dp[0] = 0

    for i in range(M):
        for k in range(2 ** N + 1):
            next = C[i] | k
            if next >= (2 ** N + 1):
                continue
            dp[next] = min(dp[next], dp[k] + A[i])

    if dp[2 ** N - 1] == float("inf"):
        print(-1)
    else:
        print(dp[2 ** N - 1])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

input = sys.stdin.readline


def main():
    N, M = [int(x) for x in input().split()]
    A = []
    C = []
    for _ in range(M):
        a, b = [int(x) for x in input().split()]
        A.append(a)
        c = [int(x) for x in input().split()]
        tmp = 0
        for cc in c:
            tmp |= 1 << (cc - 1)

        C.append(tmp)

    dp = [float("inf")] * (2 ** N + 1)

    dp[0] = 0

    for i in range(M):
        for k in range(2 ** N + 1):
            next = C[i] | k
            if next >= (2 ** N + 1):
                continue
            dp[next] = min(dp[next], dp[k] + A[i])

    if dp[2 ** N - 1] == float("inf"):
        print(-1)
    else:
        print(dp[2 ** N - 1])


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

N = int(input())
A = [int(input()) for _ in range(N)]
ans = 0
while True:
    tmp = -1
    for i in range(N):
        if A[i] > tmp:
            tmp = A[i]
            A[i] = -1
    if tmp == -1:
        break
    ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)][::-1]
def LIS(L):
  from bisect import bisect
  seq=[]
  for i in L:
    pos=bisect(seq,i)
    if len(seq)<=pos:
      seq.append(i)
    else:
      seq[pos]=i
  return len(seq)
print(LIS(A))
### BUGGY CODE ###

#ダイクストラ法
import heapq
def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [10**18] * h*w
    used = [True] * h*w #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d


h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
ch-=1
cw-=1
dh-=1
dw-=1
s=[input() for _ in range(h)]
edge=[[] for _ in range(h*w)]
for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            continue
        idx=i*w+j
        for dx in range(-2,3):
            for dy in range(-2,3):
                nx=i+dx
                ny=j+dy
                if 0<=nx<h and 0<=ny<w:
                    idx1=nx*w+ny
                    if dx==0 and dy==0:
                        continue
                    if (dx,dy) in [(-1,0),(0,-1),(1,0),(0,1)]:
                        edge[idx].append([0,idx1])
                    else:
                        edge[idx].append([1,idx1])
s=ch*w+cw
g=dh*w+dw
d=dijkstra_heap(s)
ans=d[g]
if ans==10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

def main():
    import sys
    input=sys.stdin.readline
    #ダイクストラ法
    import heapq
    def dijkstra_heap(st):
        infi=10**18
        #始点sから各頂点への最短距離
        d = [infi] * h*w
        d[st] = 0
        edgelist = [(0,st)]
        while edgelist:
            dist,idx = heapq.heappop(edgelist)
            x=idx//w
            y=idx%w
            for dx in range(-2,3):
                for dy in range(-2,3):
                    nx=x+dx
                    ny=y+dy
                    if not (0<=nx<h and 0<=ny<w):
                        continue
                    if dx==0 and dy==0:
                        continue
                    if s[nx][ny]=="#":
                        continue
                    idx1=nx*w+ny
                    if abs(dx)+abs(dy)==1:
                        if d[idx1]>dist:
                            d[idx1]=d[idx]
                            heapq.heappush(edgelist,(d[idx1],idx1))
                    else:
                        if d[idx1]>dist+1:
                            d[idx1]=dist+1
                            heapq.heappush(edgelist,(d[idx1],idx1))
        return d


    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    dh,dw=map(int,input().split())
    ch-=1
    cw-=1
    dh-=1
    dw-=1
    s=[input() for _ in range(h)]
    st=ch*w+cw
    g=dh*w+dw
    d=dijkstra_heap(st)
    ans=d[g]
    if ans==10**18:
        print(-1)
    else:
        print(ans)
if __name__=="__main__":
    main()
### BUGGY CODE ###

N = int(input())

ans = 0
for i in range(N):
    ans += i

print(ans)

### FIXED CODE ###

N = int(input())

ans = N * int(N - 1)

ans = ans // 2

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

n = int(input())
a = [0] + [int(input()) for i in range(n)]

match = []
counter = 0
now = 1
for i in range(n):
    if now == 2:
        print(counter)
        exit()

    elif now not in match:
        match += [now]
        now = a[now]
        counter += 1

    else:
        print("-1")
        exit()

### FIXED CODE ###

n = int(input())
a = [0] + [int(input()) for i in range(n)]

match = []
counter = 0
now = 1
for i in range(n):
    if now == 2:
        print(counter)
        exit()

    else:
        now = a[now]
        counter += 1

print("-1")
### BUGGY CODE ###

import functools
import operator
prod = functools.partial(functools.reduce, operator.mul)
n = int(input())
a = list(map(int, input().split()))
ans = prod(a)

if ans <= 10**18:
  print(ans)
else:
  print(-1)


### FIXED CODE ###

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

n = int(input())

s = [""] * n
t = [""] * n

cnt = 0

for i in range(n):
    s[i] = input()
    t[i] = sorted(s[i])

t = sorted(t)

for i in range(n - 1):
    for j in range(i + 1, n):
        if t[i] == t[j]:
            cnt += 1

print(cnt)


### FIXED CODE ###

n = int(input())

s = [""] * n
t = [""] * n

cnt = 0
flg = 0

for i in range(n):
    s[i] = input()
    t[i] = sorted(s[i])

t = sorted(t)

for i in range(n - 1):
    if t[i] == t[i + 1]:
        flg += 1
        cnt += flg
    else:
        flg = 0

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

import numpy as np
h,w,a,b = map(int,input().split())
x = np.ones(w, int)
x[a:] = -1
y = np.ones(h, int)
y[b:] = -1
#x = np.array([1]*a + [-1]*(w-a), int)
#y = np.array([1]*b + [-1]*(h-b), int).reshape(-1,1)
#m = x * y.reshape(-1,1)
#print(m)
#m *= m > 0
#print(m)
for i in range(h):
  row = x * y[i]
  row *= row > 0
  print(*row, sep='')

### FIXED CODE ###

h,w,a,b = map(int,input().split())
x = '1'*a + '0'*(w-a)
xinv = '0'*a + '1'*(w-a)
for i in range(h):
  row = x if i < b else xinv
  print(row)
### BUGGY CODE ###

import re

N, Q = map(int, input().split())
S = input().rstrip()

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



### FIXED CODE ###

N, Q = map(int, input().split())
S = input().rstrip()

cs = [0]
cnt = 0

for i in range(N-1):
    if S[i:i+2] == 'AC':
        cnt += 1
    cs.append(cnt)

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

def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
q = int(input())
rl = [map(int, input().split()) for _ in range(q)]

li = get_sieve_of_eratosthenes(10**5+1)
pli = [False] * (10**5+1)

for i in li:
  pli[i] = True

# print(li)
for l, r in rl:
  cnt = 0
  for j in range(l, r + 1):
    if j % 2 == 1 and pli[j] and pli[(j + 1) // 2]:
      cnt += 1
  print(cnt)


### FIXED CODE ###

def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
q = int(input())
rl = [map(int, input().split()) for _ in range(q)]

li = get_sieve_of_eratosthenes(10**5+1)
pli = [False] * (10**5+1)

for i in li:
  pli[i] = True

# print(pli)
  
# print(li)
cpli = [0] * (10**5+1)

cnt = 0
for i in range(10**5+1):
  if i % 2 == 1 and pli[i] and pli[(i + 1) // 2]:
    cnt += 1
  cpli[i] = cnt

# print(cpli)
  
for l, r in rl:
  print(cpli[r] - cpli[l-1])
### BUGGY CODE ###

from collections import defaultdict
r,c,k=map(int,input().split())
d=defaultdict(int)
for i in range(k):
  a1,a2,a3=map(int,input().split())
  d[a1*10**4+a2]=a3
dp0=[[0 for i in range(c+1)] for j in range(r+1)]
dp1=[[0 for i in range(c+1)] for j in range(r+1)]
dp2=[[0 for i in range(c+1)] for j in range(r+1)]
dp3=[[0 for i in range(c+1)] for j in range(r+1)]
for i in range(r):
  for j in range(c):
    x=d[i*10**4+j+1]
    y=d[(i+1)*10**4+j]
    dp3[i+1][j+1]=max(dp0[i][j+1]+x,dp1[i][j+1]+x,dp2[i][j+1]+x,dp3[i][j+1],dp2[i+1][j]+y,dp3[i+1][j])
    dp2[i+1][j+1]=max(dp0[i][j+1]+x,dp1[i][j+1]+x,dp2[i][j+1]+x,dp3[i][j+1],dp1[i+1][j]+y,dp2[i+1][j])
    dp1[i+1][j+1]=max(dp0[i][j+1]+x,dp1[i][j+1]+x,dp2[i][j+1]+x,dp3[i][j+1],dp0[i+1][j]+y,dp1[i+1][j])
    dp0[i+1][j+1]=max(dp0[i][j+1]+x,dp1[i][j+1]+x,dp2[i][j+1]+x,dp3[i][j+1],dp0[i+1][j])
z=d[r*10**4+c]
print(max(dp0[i+1][j+1]+z,dp1[i+1][j+1]+z,dp2[i+1][j+1]+z,dp3[i+1][j+1]))

### FIXED CODE ###

from collections import defaultdict
import sys
input=sys.stdin.readline
r,c,k=map(int,input().split())
l=[0]*((r+1)*(c+1))
for i in range(k):
  a1,a2,a3=map(int,input().split())
  l[a1*(c+1)+a2]=a3
dp0=[[0 for i in range(c+1)] for j in range(r+1)]
dp1=[[0 for i in range(c+1)] for j in range(r+1)]
dp2=[[0 for i in range(c+1)] for j in range(r+1)]
dp3=[[0 for i in range(c+1)] for j in range(r+1)]
for i in range(r):
  for j in range(c):
    x=l[i*(c+1)+j+1]
    y=l[(i+1)*(c+1)+j]
    dp3[i+1][j+1]=max(dp2[i][j+1]+x,dp3[i][j+1],dp2[i+1][j]+y,dp3[i+1][j])
    dp2[i+1][j+1]=max(dp2[i][j+1]+x,dp3[i][j+1],dp1[i+1][j]+y,dp2[i+1][j])
    dp1[i+1][j+1]=max(dp2[i][j+1]+x,dp3[i][j+1],dp0[i+1][j]+y,dp1[i+1][j])
    dp0[i+1][j+1]=max(dp2[i][j+1]+x,dp3[i][j+1],dp0[i+1][j])
z=l[r*(c+1)+c]
print(max(dp2[r][c]+z,dp3[r][c]))
### BUGGY CODE ###

k=int(input())
c=float("inf")
for i in range(10**5,10**6+1):
    c=min(c,sum([int(d) for d in str(k*i)]))
print(c)    

### FIXED CODE ###

from collections import deque
k=int(input())
t=[1]*k
q=deque()
q.append((1,1))
while q:
    p,r=q.popleft()
    if p==0:
        print(r)
        break
    if t[p]:
        t[p]=0
        q.appendleft(((p*10)%k,r))
        q.append(((p+1)%k,r+1))
### BUGGY CODE ###

x = int(input())
x_mod = x % 5
i = 0
while True:
    if i - (i - x_mod) == x_mod:
        if i ** 5 - (i-x_mod)**5 == x:
            print(i, i-x_mod)
            break
    i += 1

### FIXED CODE ###

x = int(input())

for i in range(-120, 120):
    for j in range(-120, 120):
        if x == i ** 5 - j ** 5:
            print(i, j)
            exit()