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

N,k = map(int,input().split())
l = list(map(int,input().split()))
cost = [0] * N

for i in range(N):
    temp = []
    for j in range(max(0,i-k),i):
        delta = cost[j]+abs(l[i]-l[j])
        temp.append(delta)
        cost[i] = min(temp)
print(cost[N-1])

### FIXED CODE ###

N,k = map(int,input().split())
l = list(map(int,input().split()))
cost = [0] * N

for i in range(1,N):
    temp = []
    cost[i] = min([cost[j]+abs(l[i]-l[j]) for j in range(max(0,i-k),i)])
print(cost[N-1])
### BUGGY CODE ###

from math import ceil
def solve(val):
	z = 0
	for i in range(n):
		if h[i] <= val*b:
			pass
		else:
			z += ((h[i]-val*b-1)/(a-b))+1
	if z <= val:
		return True
	else:
		return False
n,a,b = map(int,raw_input().split())
h = [input() for i in range(n)]
lo,hi = 1,10**9
while lo < hi:
	mid = lo+(hi-lo)//2
	if solve(mid):
		hi = mid
	else:
		lo = mid+1
print lo

### FIXED CODE ###

from math import ceil
def solve(val):
	z = 0
	for i in range(n):
		if h[i] <= val*b:
			pass
		else:
			z += ((h[i]-val*b-1)/(a-b))+1
	if z <= val:
		return True
	else:
		return False
n,a,b = map(int,raw_input().split())
h = [input() for i in range(n)]
lo,hi = 1,10**9
while lo < hi:
	mid = lo+(hi-lo)//2
	if solve(mid):
		hi = mid
	else:
		lo = mid+1
print lo
### BUGGY CODE ###

N = int(input())
P = list(map(int,input().split()))
result = 0
nowmin = P[0]
for i in range(N):
    if P[i]>nowmin:
        pass 
    else:
        if P[i] == min(P[:i+1]):
            result += 1
            nowmin == P[i]
print(result)

### FIXED CODE ###

N = int(input())
P = list(map(int,input().split()))
result = 0
nowmin = N
for i in range(N):
    if P[i]>nowmin:
        pass 
    else:
        result += 1
        nowmin = P[i]
print(result)
### BUGGY CODE ###

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

flg = 1
for i in range(N):
  if A[i] in A[i+1:]:
    print("NO")
    flg= 0
    break
if flg:
  print("YES")


### FIXED CODE ###

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

flg = 1
for i in range(N-1):
  if A[i]==A[i+1]:
    print("NO")
    flg= 0
    break
if flg:
  print("YES")
### BUGGY CODE ###

N = int(input())
S = input()
exc = 0
ans = S.count("R") * S.count("G") * S.count("B")

for i in range(N - 2):
    for j in range(i + 1, N - 1):
        if N - 1 < j + (j - i):
            continue
        elif S[i] == S[j] or S[j + (j - i)] == S[i] or S[j + (j - i)] == S[j]:
            continue
        else:
            ans -= 1

print(ans)


### FIXED CODE ###

N = int(input())
S = [s for s in input()]
ans = S.count("R") * S.count("G") * S.count("B")

for i in range(N - 2):
    for j in range(i + 1, N - 1):
        k = j + (j - i)
        if N - 1 < k:
            continue
        if S[k] != S[i] and S[k] != S[j] and S[i] != S[j]:
            ans -= 1

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

n = input()
s = list(input())
n = int(n)
ans = 0

for i in range(n-2):
    for j in range(i,n-1):
        for k in range(j, n):
            if s[i] != s[j] and s[i] != s[k] and s[j] != s[k] and j - i != k -j:
                ans += 1
print(ans)

### FIXED CODE ###

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

r = s.count("R")
g = s.count("G")
b = s.count("B")
ans = r*g*b

for i in range(1,n):
    for j in range(min(i+1,n-i)):
        k = j*2 -i
        if j - i == k -j:
            if k <= n and s[i] != s[i+j] and s[i] != s[i-j] and s[i+j] != s[i-j]:
                ans -= 1
print(ans)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]

for i, a in enumerate(A):
    print(max(A[:i] + A[i+1:]))


### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]

mls = [-1 for _ in range(N+1)]
for i, a in enumerate(A, 1):
    mls[i] = max(mls[i-1], a)

mrs = [-1 for _ in range(N+1)]
for i, a in enumerate(A[::-1], 1):
    mrs[i] = max(mrs[i-1], a)
mrs = mrs[::-1]

for i in range(N):
    print(max(mls[i], mrs[i+1]))
### BUGGY CODE ###

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

ans = 1
for i in a:
    ans *=i

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


### FIXED CODE ###

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

ans = 1
for i in a:
    ans *=i
    if ans > (10**18):
        ans = -1
        break
if 0 in a:
    ans = 0
print(ans)
### BUGGY CODE ###

N, Q = map(int, input().split())
G = [tuple(map(int, input().split())) for _ in range(N-1)]
W = [tuple(map(int, input().split())) for _ in range(Q)]

# 木の隣接関係 (a<bは保証されている)
M = [[] for _ in range(N+1)]
for g in G:
    M[g[0]].append(g[1])

# print(M)

# 木の親子関係
P = [[] for _ in range(N+1)]
# dfs
visited = []

def dfs(start):
    Stack = [start,]
    while Stack:
        now = Stack.pop(0)
        visited[now] = 1
        for child in M[now]:
            if not visited[child]:
                Stack.append(child)

for parent in range(1, N+1):
    visited = [0,] * (N+1)
    dfs(parent)
    P[parent].extend([i for i, s in enumerate(visited) if s])

# print(P)

res = [0,] * (N+1)
for p, x in W:
    for pp in P[p]:
        res[pp] += x

print(" ".join(map(str, res[1:])))


### FIXED CODE ###

N, Q = map(int, input().split())
G = [tuple(map(int, input().split())) for _ in range(N-1)]
W = [tuple(map(int, input().split())) for _ in range(Q)]


# 親に付いている重み
r = [0,] * (N+1)
for p, x in W:
    r[p] += x



# 木の隣接関係
M = [[] for _ in range(N+1)]
for g in G:
    M[g[0]].append(g[1])
    M[g[1]].append(g[0])

# print(M)

# 木の親子関係
P = [[] for _ in range(N+1)]
visited = [0,] * (N+1)

def dfs(start):
    q = []
    q.append(start)
    while q:
        now = q.pop()
        visited[now] = 1
        for child in M[now]:
            if not visited[child]:
                r[child] += r[now]
                q.append(child)


dfs(1)

print(*r[1:])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def bit(n, k):
    return (n >> k) & 1


def solve(N: int, a: "List[List[int]]"):
    DP = [0]*(1 << N)
    flag = [False]*(1 << N)

    def rec(S):
        if flag[S]:
            return DP[S]
        flag[S] = True

        ans = 0
        for i in range(N):
            for j in range(i+1, N):
                if bit(S, i) and bit(S, j):
                    ans += a[i][j]
        T = S
        while T > 0:
            ans = max(ans, rec(S)+rec(S ^ T))
            T = (T-1) & S
        DP[S] = ans
        return ans
    print(rec((1 << N)-1))
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [[int(next(tokens)) for _ in range(N)]
         for _ in range(N)]  # type: "List[List[int]]"
    solve(N, a)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def bit(n, k):
    return (n >> k) & 1


def solve(N: int, a: "List[List[int]]"):
    DP = [0]*(1 << N)
    flag = [False]*(1 << N)

    def rec(S):
        if flag[S]:
            return DP[S]
        flag[S] = True

        ans = 0
        for i in range(N):
            for j in range(i+1, N):
                if bit(S, i) and bit(S, j):
                    ans += a[i][j]
        T = (S-1) & S
        while T > 0:
            ans = max(ans, rec(T)+rec(S ^ T))
            T = (T-1) & S
        DP[S] = ans
        return ans
    print(rec((1 << N)-1))
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [[int(next(tokens)) for _ in range(N)]
         for _ in range(N)]  # type: "List[List[int]]"
    solve(N, a)


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

import re

s = input()
n = len(s)

pattern = "(01)+|(10)+"
old_n = len(s)+1
while len(s)<old_n:
  old_n=len(s)
  s = re.sub(pattern,"", s)

print(n-len(s))

### FIXED CODE ###

import re

s = input()
n = len(s)

one = [1 if si=="1" else 0 for si in s]
tmp=sum(one)
ret = min(tmp, n-tmp)*2

print(ret)
### BUGGY CODE ###

#c

S = input()

def clean(seq):
    if len(seq) == 1:
        return seq
    
    cleaned_seq = []
    remove_flag = False
    for idx, s in enumerate(seq):
        if remove_flag:
            remove_flag = False
            continue
            
        if idx == len(seq)-1:
            cleaned_seq.append(s)
            break

        this_ = int(s)
        next_ = int(seq[idx+1])
        if this_ + next_ == 1:
            remove_flag = True
        else:
            cleaned_seq.append(s)
            
    return cleaned_seq

former_cleaned = []
cleaned = S
while(not len(cleaned) == len(former_cleaned)):
    former_cleaned = cleaned
    cleaned = clean(former_cleaned)
    
print(len(S) - len(cleaned))


### FIXED CODE ###

S = input()

save = []
flag = False
modori_flag = False
count = 0
for idx, s in enumerate(S):
    if modori_flag:
        modori_flag = False
    elif flag:
        flag = False
        continue
            
    this_ = int(s)
    if len(save) > 0 and this_ + save[-1] == 1:
        modori_flag = True
        del save[-1]
        count += 2
        continue
    if idx == len(S) -1:
        break
    next_ = int(S[idx+1])
    if this_ + next_ == 1:
        flag = True
        count += 2
        continue
        
    save.append(this_)
    
print(count)
### BUGGY CODE ###

k = int(input())
a=7
i=1
while i <= 20000:
  if a%k ==0:
    print(i)
    break
  elif i==20000 and a%k !=0:
    print("-1")
    break
  i+=1
  a = a + 7*10**(i-1)


### FIXED CODE ###

k = int(input())
if k % 2 == 0 or k%5==0:
    print(-1)
    exit()
a = 7
ans = 1
while True:
    if a % k == 0:
        print(ans)
        exit()
    a = (a*10+7) % k
    ans += 1
### BUGGY CODE ###

a,b,k = [int(i) for i in input().split()]
 
for i in range(a,b+1):
  if abs(a-i)<k or abs(b-i)<k:
    print(i)

### FIXED CODE ###

a,b,k = [int(i) for i in input().split()]
jougen = a+k-1
kagen = b-k+1

if jougen>=kagen:
  for i in range(a,b+1):
    print(i)
    
else:
  for i in range(a,jougen+1):
    print(i)
  for i in range(kagen,b+1):
    print(i)
### BUGGY CODE ###

def main():
  import sys
  input = sys.stdin.readline
  
  N,D,A = map(int,input().split())
  XH = [tuple(map(int,input().split())) for _ in range(N)]
  XH.sort(key=lambda x:x[0])
  #print(XH)

  B = set()
  ans = 0
  for x,h in XH:
    BB = set()
    for s,t,c in B:
      #print(s,t,c,x)
      if s <= x <= t:
        h -= A*c
        BB.add((s,t,c))
    #print(h)
    if h > 0:
      BB.add((x,x+2*D,(h+A-1)//A))
      ans += (h+A-1)//A
    #print(ans,x,x+2*D,(h+A-1)//A,B)
    B = BB
  print(ans)

if __name__ == '__main__':
  main()

### FIXED CODE ###

def main():
  import sys
  from heapq import heappush, heappop, heapify
  input = sys.stdin.readline
  
  N,D,A = map(int,input().split())
  hq = []
  for i in range(N):
    x,h = map(int,input().split())
    hq.append((x,0,h))
  heapify(hq)

  ans = 0
  b = 0
  while(len(hq) > 0):
    x,a,h = heappop(hq)
    if a == 0:
      if b < h:
        cnt = ((h-b)+A-1)//A
        ans += cnt
        b += A*cnt
        heappush(hq, (x+2*D,1,A*cnt))
    else:
      b -= h
  
  print(ans)

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


N = int(input())
X = list(map(int, input().split()))

MAX = 10 ** 6 + 1
prime = [True] * MAX
counted = set()
for v in X:
    if v in counted:
        prime[v] = False
    for j in range(2 * v, MAX, v):
        prime[j] = False
    counted.add(v)

ans = 0
for v in X:
    ans += int(prime[v])
print(ans)


### FIXED CODE ###

from collections import Counter

N, *A = map(int, open(0).read().split())

m = max(A) + 1
ok = [True] * m
ctr = Counter(A)
ans = 0
for a in sorted(A):
    if ok[a] and ctr[a] == 1:
        ans += 1
        
    for j in range(2 * a, m, a):
        ok[j] = False
            
print(ans)
### BUGGY CODE ###

a,b = list(map(int, input().split()))
ans = 0

if 3*a < b:
  print(ans)
else:
  for i in range(a+1):
    if i > b:
      continue
    else:
      if i+2*a < b:
        continue
      else:
        for j in range(a+1):
          if i+j > b:
            continue
          else:
            if i+j+a < b:
              continue
            else:
              for k in range(a+1):
                if i+j+k == b:
                  ans += 1
              
  print(ans)

### FIXED CODE ###

k,s = list(map(int, input().split()))
ans = 0
for x in range(k+1):
  mx = min(k, s-x)
  mn = max(0, s-x-k)
  ans += max(0, mx-mn+1)
print(ans)
### BUGGY CODE ###

N = int(input())
lenN = len(str(N))
sumN = 0
for i in range(lenN):
  sumN += (N%10)
  N = N//10

if sumN%9 == 0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

N = list(input())
sumN = 0

for i in range(len(N)):
  sumN += int(N[i])

if sumN % 9 == 0:
  print('Yes')
else:
  print('No')
### BUGGY CODE ###

from collections import defaultdict
import sys


sys.setrecursionlimit(10 ** 6)


def find_path_on_tree(adj, to_node, node, parent=None):
    if node == to_node:
        return [to_node]
    for child in adj[node]:
        if child == parent:
            continue
        p = find_path_on_tree(adj, to_node, child, node)
        if p is None:
            continue
        return [node] + p
    return None


def depth(adj, node, parent=None):
    ret = 0
    for child in adj[node]:
        if child == parent:
            continue
        d = depth(adj, child, node) + 1
        ret = max(ret, d)
    return ret


def main():
    N, U, V = list(map(int, input().split(' ')))
    U -= 1
    V -= 1
    adj = defaultdict(list)
    for _ in range(N - 1):
        A, B = list(map(lambda x: int(x) - 1, input().split(' ')))
        adj[A].append(B)
        adj[B].append(A)
    path = find_path_on_tree(adj, U, V)  # to U from V
    dist = len(path) - 1
    partial_depth = depth(adj, path[(dist // 2) + 1], path[dist // 2])
    print(partial_depth + (dist // 2))


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import defaultdict
import sys


sys.setrecursionlimit(10 ** 6)


def depth(adj, node, parent=None):
    ret = 0
    for child in adj[node]:
        if child == parent:
            continue
        d = depth(adj, child, node) + 1
        ret = max(ret, d)
    return ret


def main():
    N, U, V = list(map(int, input().split(' ')))
    U -= 1
    V -= 1
    adj = defaultdict(list)
    for _ in range(N - 1):
        A, B = list(map(lambda x: int(x) - 1, input().split(' ')))
        adj[A].append(B)
        adj[B].append(A)

    path = [-1] * N

    def find_path_on_tree(to_node, node, parent=None, d=0):
        if node == to_node:
            path[d] = node
            return True
        for child in adj[node]:
            if child == parent:
                continue
            if not find_path_on_tree(to_node, child, node, d + 1):
                continue
            path[d] = node
            return True
        return False

    find_path_on_tree(U, V)  # to U from V
    path = [node for node in path if node != -1]
    dist = len(path) - 1
    partial_depth = depth(adj, path[(dist // 2) + 1], path[dist // 2])
    print(partial_depth + (dist // 2))


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

nums = int(input())
ary  = list(map(int,input().split()))
count =0
max_count = 0
ary.sort()

for x in ary:
    count += ary.count(x-1)
    count += ary.count(x)
    count += ary.count(x+1)
    if count > max_count:
        max_count = count
    count = 0

print(max_count)

### FIXED CODE ###

nums = int(input())
ary  = list(map(int,input().split()))
count =0
max_count = 0
ary.sort()
ary_count = [0 for i in range(100005)]
ary_count.append(0)

for i in ary:
    ary_count[i] += 1

for i in range(1,100005):
    count += ary_count[i]
    count += ary_count[i+1]
    count += ary_count[i-1]
    if count > max_count:
        max_count = count
    count = 0
print(max_count)
### BUGGY CODE ###

N, X = list(map(int, input().split()))
X_l = list(map(int, input().split()))

def golden_search(func, l,r):
  # 最小値を求める
  phi = 1.618 # phi=2とすると三分探索
  if l >= r-4:
    return min([func(k) for k in range(l,r+1)])

  c1 = int((phi/(1+phi))*l + (1/(1+phi))*r)
  c2 = int((1/(1+phi))*l + (phi/(1+phi))*r)
  if func(c1) < func(c2):
    r = c2
  elif func(c1) >= func(c2):
    l = c1
  return golden_search(func, l,r)

def Ktimes(k):
  ret = X*k + X*N
  ret += 2* sum(X_l[::-1][:k])
  ret += sum([(2*(i//k)+3)*x for i,x in enumerate(X_l[::-1])])
  return ret

answer = golden_search(Ktimes, 1, N)
print(answer)


### FIXED CODE ###

N, X = list(map(int, input().split()))
X_l = list(map(int, input().split()))

def golden_search(func, l,r):
  # 最小値を求める
  phi = 1.618 # phi=2とすると三分探索
  if l >= r-4:
    return min([func(k) for k in range(l,r+1)])

  c1 = int((phi/(1+phi))*l + (1/(1+phi))*r)
  c2 = int((1/(1+phi))*l + (phi/(1+phi))*r)
  if func(c1) < func(c2):
    r = c2
  elif func(c1) >= func(c2):
    l = c1
  return golden_search(func, l,r)

memo = {}
def Ktimes(k):
  if k not in memo:
    memo[k] = X*k + X*N
    memo[k] += 2* sum(X_l[::-1][:k])
    memo[k] += sum([(2*(i//k)+3)*x for i,x in enumerate(X_l[::-1])])
  return memo[k]

answer = golden_search(Ktimes, 1, N)
print(answer)
### BUGGY CODE ###

MOD = 10**9+7
n = int(input())
m = n - 1
x = list(map(int, input().split()))
d = [x[i+1] - x[i] for i in range(m)]

inv = [0, 1]
for i in range(2, n):
  inv += [inv[MOD % i] * (MOD - int(MOD / i)) % MOD]

s = 1
for i in range(2, n):
    s *= i
    s %= MOD

ans = sum(d) * s % MOD

for i in range(m):
    p = 1
    for j in range(i+1, n-1):
        c = j - i
        p *= c * inv[c+1]
        p %= MOD
        ans += d[j] * p * s
        ans %= MOD

print(ans)


### FIXED CODE ###

MOD = 10**9+7
n = int(input())
m = n - 1
x = list(map(int, input().split()))
d = [x[i+1] - x[i] for i in range(m)]

inv = [0, 1]
for i in range(2, n):
  inv += [inv[MOD % i] * (MOD - int(MOD / i)) % MOD]

s = 1
for i in range(2, n):
    s *= i
    s %= MOD

ans = s * sum(d) % MOD

p = 0
for i in range(1, m):
    p += inv[i+1]
    p %= MOD
    ans += s * d[i] * p
    ans %= MOD

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

import itertools 
def take_solve(take):
    result=float("inf")
    for x,y,z in itertools.permutations(take):
        result=min(result,abs(x-a)+abs(y-b)+abs(z-c))
    return result
 
n,a,b,c=[int(x) for x in input().split()]
l=[]
for _ in range(n):
    l.append(int(input()))
from collections import defaultdict
d=defaultdict(int)
def ans(takes):
    takes=sorted(takes)
    key=str(takes)
    if key in d.keys():
        return d[key]
    m=len(takes)
    result=float("inf")
    if m==3:
        result=min(result,take_solve(takes)+10*(n-m))
    else:
        for i,j in itertools.combinations(list(range(m)),2):
            next_take=[takes[x] for x in range(m) if not x in (i,j)]
            next_take.append(takes[i]+takes[j])
            result=min(result,ans(next_take))
        for i,j,k in itertools.combinations(list(range(m)),3):
            result=min(result,take_solve((takes[i],takes[j],takes[k]))+10*(n-m))
    d[key]=result
    return result
print(ans(l))

### FIXED CODE ###

import itertools 
def take_solve(take):
    result=float("inf")
    for x,y,z in itertools.permutations(take):
        result=min(result,abs(x-a)+abs(y-b)+abs(z-c))
    return result

n,a,b,c=[int(x) for x in input().split()]
l=[]
for _ in range(n):
    l.append(int(input()))
from collections import defaultdict
d=defaultdict(int)
def ans(takes):
    takes=sorted(takes)
    key=str(takes)
    if key in d.keys():
        return d[key]
    m=len(takes)
    result=float("inf")
    if m==3:
        result=min(result,take_solve(takes)+10*(n-m))
    else:
        for i,j in itertools.combinations(list(range(m)),2):
            next_take=[takes[x] for x in range(m) if not x in (i,j)]
            next_take.append(takes[i]+takes[j])
            result=min(result,ans(next_take))
        for i,j,k in itertools.combinations(list(range(m)),3):
            result=min(result,take_solve((takes[i],takes[j],takes[k]))+10*(n-m))
    d[key]=result
    return result
print(ans(l))
### BUGGY CODE ###

n, k = map(int, input().split())
h = [int(i) for i in input().split()]

dp = [0] * n

for i in range(1, n):
  dp[i] = min([dp[i-j]+abs(h[i]-h[i-j]) for j in range(1, min(i, k)+1)])

print(dp[n-1])

### FIXED CODE ###

n, k = map(int, input().split())
h = [int(i) for i in input().split()]

dp = [0] * n

for i in range(1, n):
  dp[i] = min([dp[i-j]+abs(h[i]-h[i-j]) for j in range(1, min(i, k)+1)])

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

n, k = map(int,input().split())
ans = []
for i in range(n):
    a, b = map(int,input().split())
    for j in range(b):
        ans.append(a)
#print(ans)

ans.sort()

print(ans[k - 1])

### FIXED CODE ###

n, k = map(int,input().split())
ans = [0]*100000
for i in range(n):
    a, b = map(int,input().split())
    ans[a-1] += b
#print(ans)

counter = 0

while(k > 0):
    k -= ans[counter]
    counter += 1

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

import sys
readline = sys.stdin.readline
read = sys.stdin.read

R, C, K = map(int, readline().split())
g = [[-float('inf')]*C for _ in range(R)]
for i in range(K):
    r, c, k = map(int, readline().split())
    r -= 1
    c -= 1
    g[r][c] = k

dp = [[[0]*4 for _ in range(C+1)] for _ in range(R+1)]
for r in range(R):
    for c in range(C):
        # k[0..3] = 0個拾っている状態から3個拾っている状態
        # indexが大きいほど、小さいアイテムとなるので、小さいものから更新していく
        for k in range(2, -1, -1):
            dp[r][c][k+1] = max(
                dp[r][c][k+1],
                dp[r][c][k]+g[r][c]
            )

        for k in range(4):
            dp[r+1][c][0] = max(dp[r+1][c][0], dp[r][c][k])
            dp[r][c+1][k] = max(dp[r][c+1][k], dp[r][c][k])
print(max(dp[R-1][C-1]))


### FIXED CODE ###

R, C, K = map(int, input().split())
g = [[-float('inf')]*C for _ in range(R)]
for i in range(K):
    r, c, k = map(int, input().split())
    r -= 1
    c -= 1
    g[r][c] = k

dp = [[[0]*(C+1) for _ in range(R+1)] for _ in range(4)]
for r in range(R):
    for c in range(C):
        # k[0..3] = 0個拾っている状態から3個拾っている状態
        # indexが大きいほど、小さいアイテムとなるので、小さいものから更新していく
        for k in range(2, -1, -1):
            dp[k+1][r][c] = max(
                dp[k+1][r][c],
                dp[k][r][c]+g[r][c]
            )

        for k in range(4):
            dp[0][r+1][c] = max(dp[0][r+1][c], dp[k][r][c])
            dp[k][r][c+1] = max(dp[k][r][c+1], dp[k][r][c])

ans = 0
for i in range(4):
    ans = max(dp[i][R-1][C-1], ans)
print(ans)
### BUGGY CODE ###

MOD = 998244353
N, S = map(int, input().split())
A = list(map(int, input().split()))

dp = [[0 for i in range(S + 1)] for j in range(N + 1)]

dp[0][0] = 1

for i in range(N):
    for j in range(S + 1):
        dp[i+1][j] += dp[i][j] * 2
        dp[i+1][j] %= MOD
        if j + A[i] <= S:
            dp[i + 1][j + A[i]] += dp[i][j]
            dp[i + 1][j + A[i]] %= MOD
print(dp[N][S])


### FIXED CODE ###

MOD = 998244353
N, S = map(int, input().split())
A = list(map(int, input().split()))

dp = [[0 for i in range(S + 1)] for j in range(N + 1)]

dp[0][0] = 1

for i in range(N):
    for j in range(S + 1):
        dp[i+1][j] += dp[i][j] * 2
        dp[i+1][j] %= MOD
        if j + A[i] <= S:
            dp[i + 1][j + A[i]] += dp[i][j]
            dp[i + 1][j + A[i]] %= MOD
print(dp[N][S])
### BUGGY CODE ###

n, x, m = map(int, input().split())
arr = [x]
mod = x

def find_value(lst, value):
    return [i for i, x in enumerate(lst) if x == value]

ans = 0
for i in range(n-1):
    mod = mod ** 2 % m
    res = find_value(arr, mod)

    if res: 
        j = res[0]
        a = i + 1 - j
        q, mod = divmod((n - j), a)
        ans = sum(arr[0:j]) + q * sum(arr[j:j+a]) + sum(arr[j:j+mod])
        break
    arr.append(mod)

if ans == 0:
    ans = sum(arr)

print(ans)

### FIXED CODE ###

n, x, m = map(int, input().split())
arr = [x]
mod = x
memo = [-1 for _ in range(m+1)]

ans = 0
for i in range(1, n):
    mod = mod ** 2 % m
    idx = memo[mod]

    if idx != -1:
        a = i - idx
        q, _mod = divmod((n - idx), a)

        ans = sum(arr[0:idx]) + q * sum(arr[idx:idx+a]) + sum(arr[idx:idx+_mod])
        break
    arr.append(mod)
    memo[mod] = i

if ans == 0:
    ans = sum(arr)

print(ans)