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

N,K=map(int,input().split())
A=list(map(int,input().split()))
nA=[a for a in A if a<0]
zero=[a for a in A if a==0]
pA=[a for a in A if a>0]
nA.sort(reverse=True)
pA.sort()

#積がx以下になる組み合わせの数
def f(x):
    ret=0
    if x<0:
        for na in nA:
            ret+=g2(pA,na,x)
        for pa in pA:
            ret+=g2(nA,pa,x)
    elif x==0:
        ret+=len(nA)*len(pA)*2
        ret+=len(zero)*(N-len(zero)+N-1)
    else:
        ret+=len(nA)*len(pA)*2
        ret+=len(zero)*(N-len(zero)+N-1)
        for na in nA:
            ret+=g1(nA,na,x)-(1 if na*na<=x else 0)
        for pa in pA:
            ret+=g1(pA,pa,x)-(1 if pa*pa<=x else 0)
    return ret//2

#単調増加の場合の組み合わせ数
def g1(L,n,x):
    if len(L)==0: return 0
    if L[0]*n>x: return 0
    l=0
    over=len(L)
    while over-l>1:
        m=(over+l)//2
        if L[m]*n<=x: l=m
        else: over=m
    return l+1

#単調減少の場合の組み合わせ数
def g2(L,n,x):
    if len(L)==0: return 0
    if L[-1]*n>x: return 0
    under=-1
    r=len(L)-1
    while r-under>1:
        m=(under+r)//2
        if L[m]*n<=x: r=m
        else: under=m
    return len(L)-r

#組み合わせがK個未満になる最大のxを求める(l)
l=-10**18-1
r=10**18+1
while r-l>1:
    m=(r+l)//2
    if f(m)<K: l=m
    else: r=m
print(r)


### FIXED CODE ###

import sys
input = sys.stdin.readline
N,K=map(int,input().split())
A=list(map(int,input().split()))
nA=[a for a in A if a<0]
zero=[a for a in A if a==0]
pA=[a for a in A if a>0]
nA.sort(reverse=True)
pA.sort()

pR=0
neg=len(nA)*len(pA)*2
zzz=len(zero)*(N-len(zero)+N-1)

#積がx以下になる組み合わせの数
def f(x):
    global pR
    ret=0
    if x<0:
        pR=len(pA)-1
        for na in nA:
            while pR>=0:
                if na*pA[pR]>x: break
                pR-=1
            ret+=len(pA)-pR-1
    elif x==0:
        ret+=neg
        ret+=zzz
        ret//=2
    else:
        ret+=neg
        ret+=zzz
        pR=len(nA)-1
        for na in nA:
            while pR>=0:
                if na*nA[pR]<=x: break
                pR-=1
            ret+=pR+1
            ret-=1 if na*na<=x else 0
        pR=len(pA)-1
        for pa in pA:
            while pR>=0:
                if pa*pA[pR]<=x: break
                pR-=1
            ret+=pR+1
            ret-=1 if pa*pa<=x else 0
        ret//=2
    return ret
#組み合わせがK個未満になる最大のxを求める(l)
l=-10**18-1
r=10**18
while r-l>1:
    m=(r+l)//2
    if f(m)<K: l=m
    else: r=m
print(r)
### BUGGY CODE ###

import bisect
from collections import Counter, deque
from itertools import combinations, accumulate
from math import factorial
from operator import neg
n, a = list(map(int, input().split()))
xs = list(map(lambda x: int(x) - a, input().split()))

xs.sort()
l, r = bisect.bisect_left(xs, 0), bisect.bisect_right(xs, 0)
low, n0, high = xs[:l], r - l, xs[r:]
if len(low) > len(high):
    low, high = list(map(neg, high)), list(map(neg, low))
else:
    high = high[::-1]
acc = list(accumulate(high[::-1]))[::-1]
factor = 2 ** n0
lsums = sum((Counter(map(sum, combinations(low, 1 + i))) for i in range(len(low))), Counter())

ans = 0
for lsum, cnt in lsums.items():
    tmp = 0
    q = deque()
    q.append((0, lsum))
    while len(q) > 0:
        i, v = q.popleft()
        if i >= len(high):
            continue
        if v + acc[i] < 0:
            continue
        q.append((i + 1, v))
        v += high[i]
        if v == 0:
            tmp += 1
            continue
        if v > 0:
            continue
        q.append((i + 1, v))
    ans += tmp * cnt

ans *= factor
ans += 2 ** n0 - 1

print(ans)

### FIXED CODE ###

import bisect
from collections import Counter, deque
from itertools import combinations, accumulate
from math import factorial
from operator import neg
n, a = list(map(int, input().split()))
xs = list(map(lambda x: int(x) - a, input().split()))

xs.sort()
l, r = bisect.bisect_left(xs, 0), bisect.bisect_right(xs, 0)
low, n0, high = list(map(neg, xs[:l][::-1])), r - l, xs[r:]

def sums(arr):
    cntr = Counter([0])
    for v in arr:
        tmps = tuple(cntr.items())
        for u, cnt in tmps:
            cntr[u + v] += cnt
    del cntr[0]
    return cntr

lsums = sums(low)
hsums = sums(high)

ans = sum(hsums[a] * b for a, b in lsums.items())

ans *= 2 ** n0
ans += 2 ** n0 - 1

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

import functools
import operator
N=int(input())
A=[int(x) for x in input().split()]
result = functools.reduce(operator.mul, A)
if result>10**18:
    print(-1)
else:
    print(result)

### FIXED CODE ###

N=int(input())
A=[int(x) for x in input().split()]
A.sort(reverse=True)
result=1
if 0 in A:
    print(0)

else:
    for i in A:
        result*=i
        if result>10**18:
            print(-1)
            break
    else:
        print(result)
### BUGGY CODE ###

def slove(n, a_list):

    dp = [[0]*(n+1) for i in range(n+1)]
    for i in range(n):
        for j in range(n-i):
            dp[i+1][j] = max(dp[i+1][j],
                         dp[i][j]+a_list[i+j][0]*abs(a_list[i+j][1]-i))
            dp[i][j+1] = max(dp[i][j+1],
                         dp[i][j]+a_list[i+j][0]*abs((n-1-j)-a_list[i+j][1]))

    return max([max(i) for i in dp])

if __name__ == "__main__":
    n = int(input())
    k = sorted([(int(x),i) for i,x in enumerate(input().split())], reverse=True)
    print(slove(n, k))


### FIXED CODE ###

def slove(n, a_list):

    dp = [[0]*(n+1) for i in range(n+1)]
    for i in range(n):
        for j in range(n-i):
            dp[i+1][j] = max(dp[i+1][j],
                         dp[i][j]+a_list[i+j][0]*abs(a_list[i+j][1]-i))
            dp[i][j+1] = max(dp[i][j+1],
                         dp[i][j]+a_list[i+j][0]*abs((n-1-j)-a_list[i+j][1]))

    return max([max(i) for i in dp])

if __name__ == "__main__":
    n = int(input())
    k = sorted([(int(x),i) for i,x in enumerate(input().split())], reverse=True)
    print(slove(n, k))
### BUGGY CODE ###

a, b, c, k = map(int, input().split())
abc = []
for i in range(a):
    abc.append(1)

for j in range(b):
    abc.append(0)

for l in range(c):
    abc.append(-1)

print(sum(abc[0:k]))

### FIXED CODE ###

a, b, c, k = map(int, input().split())
ans = 0
if a >= k :
    ans += k
elif a < k :
    ans += a
    if b >= (k-a):
        ans += 0
    elif b < (k-a) :
        ans += ((k-a)-b)*-1

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

n = int(input())
a = list(map(int,input().split()))
ans = 0
while all(A%2 == 0 for A in a):
 a = (i/2 for i in a )
 ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 0
while all(A%2 == 0 for A in a):
	a = [i/2 for i in a ]
	ans += 1
print(ans)
### BUGGY CODE ###

import math
from itertools import product
from collections import Counter


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def sums(a, N):
    ans = ((N//a)*((N//a)+1)//2)*a
    return ans


colors = set(['R', 'G', 'B'])

    

def solve():
    N = read_int()
    S = input().strip()
    right = Counter(S)
    left = Counter()
    total = 0
    for i in range(N):
        take = S[i]
        right[take] -= 1
        #
        for j in range(i):
            if S[j] != S[i]:
                color = (colors-set([S[j], S[i]])).pop()
                k = 2*i-j
                total += right[color]
                if k < N and S[k] == color:
                    total -= 1
        #
        left[take] += 1
    return total


if __name__ == '__main__':
    print(solve())


### FIXED CODE ###

import math
from itertools import product
from collections import Counter


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def sums(a, N):
    ans = ((N//a)*((N//a)+1)//2)*a
    return ans


colors = ['R', 'G', 'B']

def complement(A, B):
    for color in colors:
        if A != color and B != color:
            return color
    

def solve():
    N = read_int()
    S = input().strip()
    right = Counter(S)
    left = Counter()
    total = 0
    for i in range(N):
        take = S[i]
        right[take] -= 1
        #
        for j in range(i):
            if S[j] != S[i]:
                color = complement(S[j], S[i])
                k = 2*i-j
                total += right[color]
                if k < N and S[k] == color:
                    total -= 1
        #
        left[take] += 1
    return total


if __name__ == '__main__':
    print(solve())
### BUGGY CODE ###

# B Multiplication 2

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

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

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

### FIXED CODE ###

# B Multiplication 2

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

ans = 1
for ai in a:
  if not ans > 10**18:
    ans *= ai
  elif ai == 0:
    print(0)
    exit()

if ans > 10**18:
  print(-1)
else:
  print(ans)
### BUGGY CODE ###

S = input()

while True:
  if S[0:len(S)//2] == S[len(S)//2:len(S)-1]:
    print(len(S))
  else:
    tmp = S[0:len(S)-2]
    S = tmp

### FIXED CODE ###

S = input()
cnt = 0

for i in range(len(S)):
  if S[0:len(S)//2] == S[len(S)//2:len(S) + 1] and cnt != 0:
    print(len(S))
    exit()
  else:
    cnt += 1
    S = S[0:len(S) - 1]
### BUGGY CODE ###

N, K = [int(i) for i in input().split()]
H = [int(i) for i in input().split()]

dp = [0] * N
for i in range(1, N):
    L = []
    for j in range(max(0, i-K), i):
        L.append(dp[j] + abs(H[i] - H[j]))
    dp[i] = min(L)

print(dp[-1])

### FIXED CODE ###

def func():
    N, K = [int(i) for i in input().split()]
    H = [int(i) for i in input().split()]
    
    dp = [0]*N
    for i in range(1, N):
        L = []
        for j in range(max(0, i-K), i):
            L.append(dp[j] + abs(H[i] - H[j]))
        dp[i] = min(L)

    print(dp[-1])
    
if __name__=="__main__":
    func()
### BUGGY CODE ###

import itertools
N = int(input())
A = list(map(int,input().split()))
max = 0
comb = list(itertools.combinations(A,4))
for i in range(len(comb)):
    item = list(set(comb[i]))
    if len(item) == 2:
        if max < item[0]*item[1]:
            max = item[0]*item[1]

print(max)





### FIXED CODE ###

from collections import Counter

N = int(input())
A = list(map(int,input().split()))
c = Counter(A)
sticks = []
for i in c:
    s = c[i]
    if s >= 4:
        sticks.append(i)
    if s >= 2:
        sticks.append(i)
if len(sticks) < 2:
    print(0)
else:
    sticks.sort(reverse=True)
    print(sticks[0]*sticks[1])
### BUGGY CODE ###

N = int(input())
S = input()
ans = 0
for i in range(0,N):
    for j in range(i,N):
        if S[i] != S[j]:
            for k in range(j,N):
                if  j-i != k-j and S[i] != S[k] and S[j] != S[k]:
                    ans += 1
print(ans)


### FIXED CODE ###

N = int(input())
S = input()

# それぞれ違う文字の組み合わせの数
ans = S.count('R')*S.count('G')*S.count('B')

# j-i!=k-jの組み合わせ
for i in range(0, N-2):
    for j in range(i+1, N-1):
        k = j+j-i
        if k < N:
            if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
                ans -= 1

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

n, q = map(int,input().split())
s = str(input())
for i in range(q):
    l1, l2 = map(int, input().split())
    a = s[l1-1:l2].count("AC")
    print(a)

### FIXED CODE ###

n,q = map(int, input().split())
s= input()
counter = 0
countlist = [0, 0]

for i in range(1, n):
    if s[i] == "C" and s[i - 1] == "A":
        counter += 1
    countlist += [counter]

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

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

visited=[1]
old=1
count=0
while 1:
  new = a[old-1]
  count += 1
  if new in visited:
    print(-1)
    exit()
  if new == 2:
    print(count)
    exit()
  old = new
  visited.append(new)

### FIXED CODE ###

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

visited={1,}
old=1
count=0
while 1:
  new = a[old-1]
  count += 1
  if new in visited:
    print(-1)
    exit()
  if new == 2:
    print(count)
    exit()
  old = new
  visited.add(new)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()

n=int(input())
xs=input()
xj=xs.count("1")

x=int(xs,2)
#xip=x%(xj+1)
#xim=x%(xj-1)

i1=1<<n
for i in range(n-1,-1,-1):
    i1=i1>>1
    xi=x^i1
    if xi==0:
        print(0)
        continue
    if xs[n-1-i]=="0":
        pxi=xj+1
#        xi=(xip+i1%pxi)%pxi
#        xi=(xip+i1)%pxi
    else:
        pxi=xj-1
#        xi=(xim-i1%pxi)%pxi
#        xi=(xim-i1)%pxi
    xi=xi%pxi
    if xi==0:
        print(1)
        continue
    icnt=1
    while xi>0:
#        print("i",i,"xi",xi,"icnt",icnt)
        icnt+=1
        xi=xi%(bin(xi).count("1"))
    print(icnt)


### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()

n=int(input())
xs=input()
xj=xs.count("1")

x=int(xs,2)
xip=x%(xj+1)
if xj!=1:
    xim=x%(xj-1)

for i in range(n-1,-1,-1):
    if xs[n-1-i]=="0":
        pxi=xj+1
        i2=pow(2,i,pxi)
        xi=(xip+i2)%pxi
    elif xj==1:
        print(0)
        continue
    else:
        pxi=xj-1
        i2=pow(2,i,pxi)
        xi=(xim-i2)%pxi
    xi=xi%pxi
    if xi==0:
        print(1)
        continue
    icnt=1
    while xi>0:
#        print("i",i,"xi",xi,"icnt",icnt)
        icnt+=1
        xi=xi%(bin(xi).count("1"))
    print(icnt)
### BUGGY CODE ###

n = int(input())
members = input()

opposite = [(members[:i].count("W")) + (members[i:].count("E")) for i in range(n)]
print(min(opposite))

### FIXED CODE ###

n = int(input())
members = input()
m_e = members.count("E")
cost = m_e
costs = []
for i in range(n):
    if members[i]=="E":
        cost-=1
    if (i!=0 and members[i-1]=="W"):
        cost+=1
    costs.append(cost)
print(min(costs))
### BUGGY CODE ###

hoge = input().split()

N = int(hoge[0])
K = int(hoge[1])
p_list = []

hoge = input().split()

for i in range(N):
  p_list.append(int(hoge[i]))
  
big = 0
max_idx = 0
for i in range(N-K+1):
  _sum = sum(p_list[i:i+K])
  if _sum > big:
    big = _sum
    max_idx = i
    
ans = 0
for j in range(K):
  num = p_list[max_idx+j]
  kitaichi = (float(num) / 2) + 0.5
  ans += kitaichi
print(ans)

### FIXED CODE ###

hoge = input().split()

N = int(hoge[0])
K = int(hoge[1])

p_list = list(map(int,input().split()))
  
big = 0
s = [0] * (N+1)
for i in range(N):
  s[i+1] = s[i] + p_list[i]

res = 0
for i in range(N-K+1):
  val = s[K+i] - s[i]
  if res < val:
    res = val

ans = (float(res) / 2) + 0.5 * float(K) 
print(ans)
### BUGGY CODE ###

import sys

n, we = map(int, input().split())

cf=[(0, 0)]*(n+1)

for i in range(1, n+1):
    cf[i] = tuple( map(int, sys.stdin.readline().split()) )

dp=[0]*(we+1)

best=0

for i in range(1, n+1):
    for j in reversed(range(cf[i][0], we+1)):
        dp[j]=max( dp[j], dp[j-cf[i][0]]+ cf[i][1] )
        
    best=max(best, dp[we])


print(best)

# for i in range(1, n+1): print( dp[i], '\n' )

### FIXED CODE ###

n, we = map(int, input().split())

cf=[(0, 0)]*(n+1)

for i in range(1, n+1):
    cf[i] = tuple( map(int, input().split()) )

dp=[[0]*(we+1) for _ in range(n+1)]

best=0

for i in range(1, n+1):
    for j in range(cf[i][0]):
        dp[i][j]=dp[i-1][j]
    for j in range(cf[i][0], we+1):
        dp[i][j]=max( dp[i][j-1], dp[i-1][j], dp[i-1][j-cf[i][0]]+ cf[i][1] )
    best=max(best, dp[i][we])


print(best)

# for i in range(1, n+1): print( dp[i], '\n' )
### BUGGY CODE ###

N = int(input())
result = []
for i in range(1, N+1):
    if N % i == 0:
        result.append(i+int(N/i)-2)
print(min(result))

### FIXED CODE ###

import numpy as np
N = int(input())
result = []
for i in range(1, np.sqrt(N).astype(int)+1):
    if N % i == 0:
        result.append(i+int(N/i)-2)
print(min(result))
### BUGGY CODE ###

#! /usr/bin/env python3

# from fractions import gcd
# from math import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement
from collections import Counter, deque, defaultdict

N = int(input())
S = input()

mi = 10000000

c = Counter(S)
A = N - c["#"]
B = N - c["."]

for i in range(1, N):
    l = S[:i]
    r = S[i:]
    a = l.count("#") + r.count(".")
    if mi > a:
        mi = a

print(min(mi, A, B))


### FIXED CODE ###

from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement
from collections import Counter, deque, defaultdict

N = int(input())
S = input()

mi = 10000000

c = Counter(S)
A = N - c["#"]
B = N - c["."]

l = 0
r = c["."]

for i in range(0, N):

    if S[i] == "#":
        l += 1
    else:
        r -= 1
    a = l + r
    if mi > a:
        mi = a

print(min(mi, A, B))
### BUGGY CODE ###

import bisect
from collections import defaultdict
e=defaultdict(dict)
 
n=int(input())
a=[int(i) for i in input().split(" ")]
b=[int(i) for i in input().split(" ")]
c=[int(i) for i in input().split(" ")]

b.sort()
c.sort()
for i in b:
  e[i]=len(c)-bisect.bisect_right(c,i)
n=0

for i in a:
  
  n+=sum([e[j] for j in b[bisect.bisect_right(b,i):]] )
print(n)

### FIXED CODE ###

import bisect

n=int(input())
a=[int(i) for i in input().split(" ")]
b=[int(i) for i in input().split(" ")]
c=[int(i) for i in input().split(" ")]

a.sort()
c.sort()
lc=len(c)
print(sum([(lc-bisect.bisect_right(c,j))*(bisect.bisect_left(a,j)) for j in b]))
### BUGGY CODE ###

from fractions import gcd

MOD = 10**9 + 7
N = int(input())
A = list(map(int, input().split()))

l = A[0]
for a in A:
  l = l * a // gcd(l, a)

ans = 0
for a in A:
  ans += (l//a) % MOD

print(ans%MOD)

### FIXED CODE ###

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


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


def power(n, r, mod=10**9+7):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod


MOD = 10**9 + 7
N = int(input())
A = list(map(int, input().split()))

l = A[0]
for a in A:
  t = l%a
  if t != 0:
    l = lcm(l, a)

l %= MOD
ans = 0
for a in A:
  ans += (l * power(a, MOD-2)) % MOD
  ans %= MOD

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

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

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

print(ans)

### FIXED CODE ###

n = int(input())
s = input()
ans = s.count("R")*s.count("G")*s.count("B")


for i in range(n):
    p = s[i]
    for j in range(i,n):
        if s[j] != p:
            q = s[j]
            if 2 * j - i < n:
                if s[2*j-i] != p and s[2*j-i] != q:
                     ans -= 1

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

N,K=map(int,input().split())
p=list(map(int,input().split()))
k=[0]*(N-K+1)
for i in range(N-K+1):
    k[i]=sum(p[i:i+K])
print((max(k)+K)/2)

### FIXED CODE ###

N,K=map(int,input().split())
p=list(map(int,input().split()))
a=sum(p[0:K])
k=[a]+[0]*(N-K)
for i in range(N-K):
    a=a-p[i]+p[K+i]
    k[i+1]=a
print((max(k)+K)/2)
### BUGGY CODE ###

n, m = map(int, input().split())
ab = []
for i in range(m):
	a, b = map(int, input().split())
	ab.append([a,b])
ab.sort()
for i in range(m):
	if ab[i][0] == 1:
		d = ab[i][1]
		for j in ab[i+1:]:
			if j[0] == d and j[1] == n:
				print ("POSSIBLE")
				exit()
print ("IMPOSSIBLE")

### FIXED CODE ###

n, m = map(int, input().split())
#2次元配列
#a=[list(map(int,input().split())) for i in range(m)]

aa = []
bb = []
for i in range (m):
	a, b = map(int, input().split())
	if(a == 1):
		aa.append(b)
	if(b == n):
		bb.append(a)

if( len(set(aa) & set(bb)) == 0):
	print ("IMPOSSIBLE")
else:
	print ("POSSIBLE")
### BUGGY CODE ###

n = int(input())
A = list(map(int,input().split()))
ans = 0
for i in range(n):
  for j in range(i+1,n):
    if j-i == A[i] + A[j]:
      ans += 1
print(ans)

### FIXED CODE ###

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

X = dict()
ans = 0
for i in range(N):
    L = i + A[i]
    if L not in X:
        X[L] = 1
    else:
        X[L] += 1

for i in range(N):
    R = i - A[i]
    if R in X:
        ans += X[R]
        
print(ans)
### BUGGY CODE ###

from numba import njit

@njit
def solve(N, X, M):
    ans = 0
    a = X
    a0 = X
    for i in range(N):
        ans += a
        a = (a ** 2) % M
        if a == 1:
            ans += (N - i - 1)
            break
        if a == a0:
            w = i + 1
            k = N // w
            m = N % w
            ans *= k
            for i in range(m):
                ans += a
                a = (a ** 2) % M
    return ans

N, X, M = [int(x) for x in input().split()]
ans = solve(N, X, M)
print(ans)

### FIXED CODE ###

import numpy as np
i8 = np.int64


def solve(N, X, M):
    memo_val = np.zeros(M, i8)
    memo_i = np.zeros(M, i8)
    ret = 0
    a = X
    for i in range(1, N):
        ret += a
        if memo_i[a] > 0:
            u = (N - memo_i[a]) // (i - memo_i[a])
            v = (N - memo_i[a]) % (i - memo_i[a])
            ret = u * (ret - memo_val[a])
            nokori = v + memo_i[a]
            for j in range(M):
                if memo_i[j] == nokori:
                    ret += memo_val[j]
            return ret
        memo_i[a] = i
        memo_val[a] = ret
        a = a ** 2 % M
    ret += a
    return ret

def main():
    f = open(0)
    N, X, M = [int(x) for x in f.readline().split()]
    ans = solve(N, X, M)
    print(ans)

main()
### BUGGY CODE ###

s = input()
K = int(input())
 
l = len(s)
 
sub = []
 
for i in range(l):
    for j in range(i+1):
        sub.append(s[j:i+1])
 
#print(sub)
subl = list(set(sub))

subl.sort()
#print(subl)
 
print(subl[K-1])

### FIXED CODE ###

import collections

s = input()
K = int(input())

l = len(s)
sub = set()

if l <= 50:
    for i in range(l):
        for j in range(i+1):
            sub.add(s[j:i+1])
    #print(sub)
    subl = list(sub)
    subl.sort()
    #print(subl)
    print(subl[K-1])

else:
    cl = collections.Counter(s).most_common()
    cl.sort(key=lambda x: x[0])
    #print(cl)
    d = 0
    while len(sub) < K:
        be = cl[d][0]
        for i in range(l):
            if s[i] == be:
                for j in range(K):
                    sub.add(s[i:min(i+j+1,l)])
        d += 1
    #print(sub)
    subl = list(sub)
    subl.sort()
    print(subl[K-1])
### BUGGY CODE ###

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

dp = [0] * N
dp[0] = 0

for i in range(1, N):
    if i < K:
        dp[i] = min([abs(hhh[i] - hhh[i - k]) + dp[i - k]
                     for k in range(1, i + 1)])
    else:
        dp[i] = \
            min([abs(hhh[i] - hhh[i - k]) + dp[i - k]
                 for k in range(1, K + 1)])

print(dp[-1])


### FIXED CODE ###

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

dp = [0] * N
dp[0] = 0

for i in range(1, N):
    if i < K:
        dp[i] = min([abs(hhh[i] - hhh[i - k]) + dp[i - k]
                     for k in range(1, i + 1)])
    else:
        dp[i] = \
            min([abs(hhh[i] - hhh[i - k]) + dp[i - k]
                 for k in range(1, K + 1)])

print(dp[-1])