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

def power(a, b, P):
	if b == 0:
		return 1
	elif b == 1:
		return a % P
	elif b % 2 == 0:
		return (power(a, b//2, P) ** 2) % P
	else:
		return (power(a, b//2, P) ** 2 * a) % P
 

N, P = (int(i) for i in input().split())
S = input()
l = [0]*N
ls = [0]*(N+1)
if P != 2 and P != 5:
    for i in range(N):
        a = int(S[N-1-i]) * power(10, i, P)
        l[i] = a%P
        ls[i+1] = (ls[i]+ l[i])%P
    d = {}
    for i in range(N+1):
        if ls[i] not in d:
            d[ls[i]] = 0
        d[ls[i]] += 1
    ans = 0
    for k in d:
        a = d[k]
        ans += (a-1)*a//2
    print(ans)
else:
    ans = 0
    for i in range(N):
        if int(S[i]) % P == 0:
            ans += (i+1)
    print(ans)

### FIXED CODE ###

def power(a, b, P):
	if b == 0:
		return 1
	elif b == 1:
		return a % P
	elif b % 2 == 0:
		return (power(a, b//2, P) ** 2) % P
	else:
		return (power(a, b//2, P) ** 2 * a) % P
 

N, P = (int(i) for i in input().split())
S = input()
l = [0]*N
ls = [0]*(N+1)
if P != 2 and P != 5:
    po = [1]*N
    for i in range(N-1):
        po[i+1] = (po[i]*10)%P
    d = [0]*P
    d[0] = 1
    b = 0
    for i in range(N):
        a = int(S[N-1-i]) * po[i]
        l[i] = a%P
        b += l[i]
        b %= P
        d[b] += 1
    ans = 0
    for a in d:
        ans += (a-1)*a//2
    print(ans)
else:
    ans = 0
    for i in range(N):
        if int(S[i]) % P == 0:
            ans += (i+1)
    print(ans)
### BUGGY CODE ###

N = int(input())
D = [int(i) for i in input().split()]
M = int(input())
T = [int(i) for i in input().split()]
cnt = [0]*M
for n in range(N):
    d = D[n]
    for m in range(M):
        if T[m] == d:
            T[m] = 0
            cnt[m] += 1
            break

if sum(cnt) == M:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

from collections import Counter
N = int(input())
D = [int(i) for i in input().split()]
M = int(input())
T = [int(i) for i in input().split()]

cD = Counter(D)

for t in T:
    if cD.get(t,0) == 0:
        print('NO')
        exit()
    else:
        cD[t] -= 1

print("YES")
### BUGGY CODE ###

N = int(input())
for h in range(1, 3501):
    for n in range(1, 3501):
        bunbo = 4 * h * n - N * n - N * h
        if bunbo > 0 and N * h * n % bunbo == 0:
            print("{} {} {}".format(h, n, N * h * n // bunbo))
            exit()

### FIXED CODE ###

N = int(input())
for h in range(1, 3501):
    for n in range(1, 3501):
        waru = 4 * h * n - N * n - N * h
        if waru != 0:
            w = (N * h * n) / waru
            if w > 0 and int(w) / w == 1:
                print("{} {} {}".format(h, n, int(w)))
                exit()
### BUGGY CODE ###

# 正解ではない

from queue import Queue

q = Queue()
cell_list = list()


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for i in range(H)]
    q.put((0, Ch - 1, Cw - 1))
    S[Ch - 1][Cw - 1] = '/'

    answer = resolve(S, (Dh - 1, Dw - 1), H, W)
    print(answer)


def resolve(S, D, H, W):
    while not q.empty():
        worp_count, x, y = q.get()
        cell_list.append((x, y))

        if (x, y) == D:
            return worp_count

        for i, j in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
            if 0 <= i < H and 0 <= j < W and S[i][j] == '.':
                q.put((worp_count, i, j))
                S[i][j] = '/'

    for x, y in cell_list:
        for i, j in [(x + a, y + b) for a in range(-2, 3) for b in range(-2, 3)]:
            if 0 <= i < H and 0 <= j < W and S[i][j] == '.':
                q.put((worp_count + 1, i, j))
                S[i][j] = '/'

    if q.empty():
        return -1

    return resolve(S, D, H, W)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    d = [[-1 for _ in range(W)] for _ in range(H)]

    q = deque([])
    q.appendleft((0, Ch - 1, Cw - 1))

    while len(q):
        worp_count, x, y = q.popleft()

        if d[x][y] != -1:
            continue
        d[x][y] = worp_count

        for i, j in ((a, b) for a in range(-2, 3) for b in range(-2, 3)):
            nx = x + i
            ny = y + j
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == '.':
                if i == 0 and j == 0:
                    continue
                elif abs(i) + abs(j) == 1:
                    q.appendleft((worp_count, nx, ny))
                else:
                    q.append((worp_count + 1, nx, ny))

    print(d[Dh - 1][Dw - 1])


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

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

if K==N+1:
    print(1)
elif K==N:
    print(N+2)
else:
    
    zentori=[]
    for i in range(2**(K-1),2**(N+1)):
        baai=[]
        for j in range(N+1):
            if (i>>j) & 1:
                baai.append(j)
        if len(baai)>=K:
            zentori.append((sum(baai),len(baai)))
    
    setzentori=set(zentori)
    print(int(len(setzentori)%(10**9+7)))

### FIXED CODE ###

N, K = map(int, input().split())
 
if K==N+1:
    print(1)
elif K==N:
    print(N+2)
else:
    def tousawa(shokou, makkou, kosu):
        return int((shokou+makkou)*kosu/2)
    
    ans=0
    for i in range(K,N+2):
        ans+=tousawa(N-i+1,N,i)-tousawa(0,i-1,i)+1
    print(int(ans%(10**9+7)))
### BUGGY CODE ###

import itertools
N,M=map(int,input().split())
cakes=[]
for i in range(N):
  x,y,z=map(int,input().split())
  cakes.append([x,y,z])
score = 0
for c in list(itertools.combinations(cakes,M)):
  c=zip(*c)
  c=map(sum,c)
  c=map(abs,c)
  c=sum(c)
  if (score < c):
    score = c
print(score)


### FIXED CODE ###

N,M=map(int,input().split())
cakes=[]
for i in range(N):
  x,y,z=map(int,input().split())
  cakes.append([x,y,z])
if M==0:
  print(0)
  quit()
score=[0]*8
score[0]=sum(sorted(map(lambda c: c[0]+c[1]+c[2], cakes))[-M:])
score[1]=sum(sorted(map(lambda c: c[0]+c[1]-c[2], cakes))[-M:])
score[2]=sum(sorted(map(lambda c: c[0]-c[1]+c[2], cakes))[-M:])
score[3]=sum(sorted(map(lambda c: c[0]-c[1]-c[2], cakes))[-M:])
score[4]=sum(sorted(map(lambda c:-c[0]+c[1]+c[2], cakes))[-M:])
score[5]=sum(sorted(map(lambda c:-c[0]+c[1]-c[2], cakes))[-M:])
score[6]=sum(sorted(map(lambda c:-c[0]-c[1]+c[2], cakes))[-M:])
score[7]=sum(sorted(map(lambda c:-c[0]-c[1]-c[2], cakes))[-M:])
print(max(score))
### BUGGY CODE ###

def main():
    s = input()
    q = int(input())

    for i in range(q):
        v = list(input().split())
        if int(v[0]) == 1:
            s = s[::-1]
        elif int(v[1]) == 1:
            s = v[2] + s
        elif int(v[1]) == 2:
            s = s + v[2]
    print(s)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    s = input()
    q = int(input())

    reverse = 0
    head = ""
    tail = ""

    for i in range(q):
        v = list(input().split())
        if int(v[0]) == 1:
            reverse += 1
        elif reverse % 2 == 0:
            if int(v[1]) == 1:
                head += v[2]
            else:
                tail += v[2]
        elif reverse % 2 == 1:
            if int(v[1]) == 1:
                tail += v[2]
            else:
                head += v[2]

    s = head[::-1] + s + tail
    if reverse % 2 == 1:
        s = s[::-1]

    print(s)


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

from functools import reduce
from itertools import permutations

def f(s):
    while True:
        t = s.replace('()', '')
        if t == s:
            return s
        s = t

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

l = 0
r = 0
for s in S:
    t = s.count('(')
    l += t
    r += len(s) - t
if l != r:
    print('No')
    exit()

S = [s for s in map(f, S) if s != ""]

if len(S) == 0:
    print('Yes')
    exit()

lS = [s for s in S if s[0] == "("]
rS = [s for s in S if s[0] == ")"]

ld = {}
for s in lS:
    ld.setdefault(s, 0)
    ld[s] += 1

rd = {}
for s in rS:
    rd.setdefault(s, 0)
    rd[s] += 1

for k1 in list(ld.keys()):
    k2 = k1[::-1]
    if k2 in rd:
        t = max(ld[k1], rd[k2])
        ld[k1] -= t
        rd[k2] -= t

if len(ld) == 0 and len(rd) == 0:
    print('Yes')
    exit()

SS = []
for k in ld:
    for i in range(ld[k]):
        SS.append(k)
for k in rd:
    for i in range(rd[k]):
        SS.append(k)

for ss in permutations(SS, len(SS)):
    t = reduce(lambda x, y: x + y, ss)
    if f(t) == '':
        print('Yes')
        exit()
print('No')


### FIXED CODE ###

def scan(s):
    m = 0
    a = 0
    for c in s:
        if c == '(':
            a += 1
        elif c == ')':
            a -= 1
        m = min(m, a)
    return m, a


def key(v):
    m, a = v
    if a >= 0:
        return 1, m, a
    else:
        return -1, a - m, a

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

c = 0
for m, a in sorted([scan(s) for s in S], reverse=True, key=key):
    if c + m < 0:
        c += m
        break
    c += a

if c == 0:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

from collections import deque
N = int(input())

def trans(x):
    return int(x)-1

A = deque()
for _ in range(N):
    A.append(deque(map(trans,input().split())))

Q = deque()

def check(i):
    if len(A[i]) == 0:
        return
    j = A[i][0]
    if len(A[j]) == 0:
        return
    if A[j][0] == i:
        if i > j:
            i, j = j, i
        Q.append([i, j])

def get_unique(q):
    r = deque()
    seen = []
    for a in q:
        if a not in seen:
            seen.append(a)
            r.append(a)
    return r


for i in range(N):
    check(i)

ans = 0
while len(Q) > 0:
    ans += 1
    Q2 = get_unique(Q)
    Q = deque()
    for q in Q2:
        A[q[0]].popleft()
        A[q[1]].popleft()
    for q in Q2:
        check(q[0])
        check(q[1])

for i in range(N):
    if len(A[i]) > 0:
        print(-1)
        exit()

print(ans)

### FIXED CODE ###

from collections import deque
N = int(input())

def trans(x):
    return int(x)-1

A = deque()
for _ in range(N):
    A.append(deque(map(trans,input().split())))

Q = set()

def check(i):
    if len(A[i]) == 0:
        return
    j = A[i][0]
    if len(A[j]) == 0:
        return
    if A[j][0] == i:
        if i > j:
            i, j = j, i
        Q.add((i, j))

for i in range(N):
    check(i)

ans = 0
while len(Q) > 0:
    ans += 1
    Q2 = Q.copy()
    Q = set()
    for q in Q2:
        A[q[0]].popleft()
        A[q[1]].popleft()
    for q in Q2:
        check(q[0])
        check(q[1])

for i in range(N):
    if len(A[i]) > 0:
        print(-1)
        exit()

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

n,m = map(int, input().split())
ans = 0
for i in range(m):
    l,r = map(int, input().split())
    tmp = set(range(l,r+1))
    if i == 0:
        ans = tmp
    else:
        ans = ans & tmp

print(len(ans))

### FIXED CODE ###

n,m = map(int, input().split())
ans = 0
L = -100000000
R = 100000000
for i in range(m):
    l,r = map(int, input().split())
    if l > L:
        L = l
    if r < R:
        R = r

print(len(range(L,R+1)))
### BUGGY CODE ###

N,X,M = map(int,input().split())
dps = [X%M]
rt = 0
while True:
  d = (dps[-1]**2)%M
  if d not in dps:
    dps.append(d)
    if N == len(dps):
      print(sum(dps))
      break
  else:
    ki = dps.index(d)
    RP = (N-ki) // len(dps[ki:])
    mod = (N-ki) % len(dps[ki:])
    print(sum(dps[:ki]) + RP*sum(dps[ki:])+sum(dps[ki:ki+mod]))
    break


### FIXED CODE ###

n, x, m = map(int, input().split())
mn = min(n, m)
P = []
sum_p = 0
X = [-1] * m
for i in range(mn):
    if X[x] > -1:
        cyc_len = len(P) - X[x]
        remain = P[X[x]]
        cyc = (sum_p - remain) * ((n - X[x]) // cyc_len)
        remain += P[X[x] + (n - X[x]) % cyc_len] - P[X[x]]
        print(cyc + remain)
        exit()
    P.append(sum_p)
    sum_p += x
    X[x] = i
    x = x*x % m
print(sum_p)
### BUGGY CODE ###

import numpy as np
n = int(input())
A = [[ord(i) for i in input()] for j in range(n)]
count = 0
for a in range(n):
    arr = np.array(A[a:][:] + A[:a][:])
    if np.allclose(arr,arr.T):
        count += n
print(count)

### FIXED CODE ###

n = int(input())
A = [input() for _ in range(n)]
# AT = list(map(''.join,zip(*A)))
count = 0
for a in range(n):
    arr = A[a:][:] + A[:a][:]
    arrT = list(map(''.join, zip(*arr)))
    for i in range(n):
        if arr[i][i+1:] != arrT[i][i+1:]:
            break
    else:
        count += n
print(count)
### BUGGY CODE ###




aa=int(input())
N=[0 for i in range(aa)]
for i in range(aa):
  bb=input()
  #print(b)
  N[i]=bb.split()




for i in range(aa):

  a=int(N[i][0])
  b=int(N[i][1])
  c=int(N[i][2])
  d=int(N[i][3])

  e=a-a//b*b
  f=d-d//b*b
  

  h=0 #YES=0 NO=1


  if a<b or d<b :
    h=1
  else:

  
    if f!=0 :
      while e<b:
        if e>c :
          h=1
          
        e+=f
        if h==1:
          break
        #print(e)
        #print(f)
  #print("while")
    else:
      if e>c :
        h=1

  

  if h==1:
    print("No")
  else:
    print("Yes")


### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
C = [list(map(int,input().split())) for i in range(n)]

from fractions import gcd

for i in range(n):
    a = C[i][0]
    b = C[i][1]
    c = C[i][2]
    d = C[i][3]
    ng = 0

    e = 0  # 最初に補充が発生する直前の本数
    e0 = a - b
    e1 = ((c - a%b) // b) * b + a%b
    e = min(e0, e1)

    if e < 0 or b > d:
        ng = 1
    else:
        g = gcd(b, d)
        # print(c+1, b-1, g)
        if c+1 <= b-1 and (c - e) // g < (b-1 - e) // g:
            ng = 1

    if ng == 1:
        print("No")
    else:
        print("Yes")
### BUGGY CODE ###

import sys
import numpy as np

def main():
    MOD = int(1e9 + 7)

    n, k = map(int, input().split())
    can = np.zeros((n,n), dtype=object)
    for i in range(n):
        for j, e in enumerate(int(c) for c in input().split()):
            can[i,j] = e

    answer = np.identity(n, dtype=object)
    while k:
        if k % 2:
            answer = np.dot(answer, can)
        can = np.dot(can, can)
        k //= 2

    total = 0
    for i in range(n):
        for j in range(n):
            total += int(answer[i,j])
            if total >= MOD:
                total -= MOD

    print(total)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import numpy as np


def main():
    MOD = int(1e9 + 7)

    n, k = map(int, input().split())
    can = [[int(c) for c in input().split()] for _ in range(n)]
    can = np.matrix(can, 'O')
    
    # for i in range(n):
    #     for j, e in enumerate(int(c) for c in input().split()):
    #         can[i, j] = e

    b = np.eye(n, n, 0, 'O')
    while k:
        b = [b, b*can % MOD][k & 1]
        can = can*can % MOD
        k >>= 1

    print(b.sum() % MOD)

    # answer = np.eye(n, dtype=int)
    # while k:
    #     if k % 2:
    #         answer = np.dot(answer, can) % MOD
    #     can = np.dot(can, can) % MOD
    #     k //= 2

    # total = 0
    # for i in range(n):
    #     for j in range(n):
    #         total += answer[i,j]
    #         if total >= MOD:
    #             total -= MOD

    # print(total)


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

import fractions
from functools import reduce

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

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

ans = 0

if n <= 10**3:
    for i in range(n):
        ans = max(gcd_list(a[:i]+a[i+1:]), ans)

    print(ans)
    exit()
else:
    n1 = n//10**3
    n2 = n%10**3

    g = []

    for i in range(n1):
        g.append(gcd_list(a[i*(10**3):(i+1)*(10**3)]))

    if n2 >0:
        g.append(gcd_list(a[n1*(10**3):]))

    for i in range(n):
        memo = g[i//(10**3)]
        g[i//(10**3)] = gcd_list(a[(i//10**3)*(10**3):i] + a[i+1:(i//10**3+1)*(10**3)])
        ans = max(gcd_list(g), ans)
        g[i // (10 ** 3)] = memo
    print(ans)


### FIXED CODE ###

import fractions

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

ans = 0

l = [0]
r = [0]

for i in range(n):
    l.append(fractions.gcd(l[i],a[i]))
    r.append(fractions.gcd(r[i],a[n-i-1]))

ans = 0

for i in range(n):
    ans = max(ans, fractions.gcd(l[i],r[n-i-1]))

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

n = input()
l = list(map(int, input().split()))
l.sort(reverse=True)
s = 0
for i in range(len(l)-2):
  longest = l[i]
  if l[i+1] + l[i+2] > longest:
    for j in range(i + 1, len(l)-1):
      second = l[j]
      ss = 0
      for k in range(j+1, len(l)):
        third = l[k]
        if second + third > longest:
          s += 1
          ss += 1
        else:
          break
      if ss == 0:
        break
print(s)

### FIXED CODE ###

from bisect import bisect_right
n = input()
l = list(map(int, input().split()))
l.sort()
s = 0
for i in range(len(l)-2):
  for j in range(i+1, len(l)-1):
    ind = bisect_right(l, l[i] + l[j] - 1)
    s += max(ind - j - 1, 0)
print(s)
### BUGGY CODE ###

def knapsack(N, W, weight, value):
  inf = float("inf")
  dp = [[-inf]*(W+1) for _ in range(N+1)]
  for i in range(W+1):
    dp[0][i] = 0
  
  for i in range(N):
    for j in range(W+1):
      if weight[i] <= j:
        dp[i+1][j] = max(dp[i][j], dp[i][j-weight[i]]+value[i])
      else:
        dp[i+1][j] = dp[i][j]
  return dp[N][W]
  
N, W = map(int, input().split())
weight, value = [], []
for i in range(N):
  w, v = map(int, input().split())
  weight.append(w)
  value.append(v)

print(knapsack(N, W, weight, value))

### FIXED CODE ###

def knapsack(N, W, weight, value):
  inf = float("inf")
  dp = [[-inf]*(W+1) for _ in range(N+1)]
  for i in range(W+1):
    dp[0][i] = 0
  
  for i in range(N):
    for j in range(W+1):
      if weight[i] <= j:
        dp[i+1][j] = max(dp[i][j], dp[i][j-weight[i]]+value[i])
      else:
        dp[i+1][j] = dp[i][j]
  return dp[N][W]
  
N, W = map(int, input().split())
weight, value = [], []
for i in range(N):
  w, v = map(int, input().split())
  weight.append(w)
  value.append(v)

print(knapsack(N, W, weight, value))
### BUGGY CODE ###

class SegTree:
  def segfunc(self,x,y):
    return x|y
  def __init__(self,a,x):
    n=len(a);self.num=1<<(n-1).bit_length();self.seg=[x if type(x)==type(1) else x.copy() for _ in range(2*self.num-1)]
    for i in range(n):self.seg[i+self.num-1]=a[i]
    for i in range(self.num-2,-1,-1):self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2])
  def update(self,k,x):
    i=k+self.num-1;self.seg[i]=x
    while i!=0:i=(i-1)>>1;self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2])
  def query(self,p,q):
    l,r=p+self.num-1,q+self.num-1
    if l==r:return self.seg[l]
    ans=self.seg[l];l+=1
    for _ in range(10000):
      if r-l<2:break
      if ~l&1:ans=self.segfunc(self.seg[l],ans)
      if r&1:ans=self.segfunc(self.seg[r],ans);r-=1
      l>>=1;r=(r-1)>>1
    ans=self.segfunc(self.seg[l],ans)
    if l!=r:ans=self.segfunc(self.seg[r],ans)
    return ans
n=int(input())
s=input()
seg=SegTree([{i}for i in s],set())
q=int(input())
for _ in range(q):
  query=input().split()
  if query[0]=="1":
    _,i,c=query
    seg.update(int(i)-1,{c})
  else:
    _,l,r=query
    print(len(seg.query(int(l)-1,int(r)-1)))

### FIXED CODE ###

import sys;input=sys.stdin.readline
n=int(input())
s=input()
num=2**(n-1).bit_length()
def segfunc(x,y):return x|y
seg=[0]*(2*num-1)
for i in range(n):seg[i+num-1]=2**(ord(s[i])-97)
for i in range(num-2,-1,-1):seg[i]=segfunc(seg[2*i+1],seg[2*i+2])
def update(i,x):
  i+=num-1;seg[i]=x
  while i:i=(i-1)//2;seg[i]=segfunc(seg[i*2+1],seg[i*2+2])
def query(l,r):
  l+=num-1;r+=num-1
  if l==r:return seg[l]
  s=seg[l];l+=1
  while r-l>1:
    if ~l%2:s=segfunc(seg[l],s)
    if r%2:s=segfunc(seg[r],s);r-=1
    l//=2;r=(r-1)//2
  if l==r:return segfunc(s,seg[l])
  return segfunc(s,segfunc(seg[l],seg[r]))
for _ in range(int(input())):
  quer=input().split()
  if quer[0]=="1":
    _,i,c=quer
    update(int(i)-1,2**(ord(c)-97))
  else:
    _,l,r=quer
    print(sum(map(int,bin(query(int(l)-1,int(r)-1))[2:])))
### BUGGY CODE ###

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

ans=0
for i in range(n):
  for j in range(i+1,n):
    for k in range(j+1,n):
      if L[i]<L[j]+L[k] and L[j]<L[k]+L[i] and L[k]<L[i]+L[j]:
        ans+=1
print(ans)

### FIXED CODE ###

import bisect
n=int(input())
L=list(map(int,input().split()))

L.sort()
ans=0
for i in range(n):
  for j in range(i+1,n):
    index=bisect.bisect_left(L,L[i]+L[j])
    ans+=index-(j+1)
    
print(ans)
### BUGGY CODE ###

def check_prime(k):
    if k == 1:return 1
    num = int(k ** 0.5 // 1)
    for i in range(2, num + 1):
        if k % i == 0:
            if check.get(i) or check.get(k//i):return 0

    return 1

n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
double = dict()
check = dict()
if n > 1:
    if a[0] == 1 and a[1] == 1:
        print(0)
        exit()
    elif a[0] == 1:
        print(1)
        exit()

for i in range(n):
    if i < n - 1 and a[i] == a[i + 1]:
        double[a[i]] = 1
        check[a[i]] = 1
        continue
    if double.get(a[i]):continue


    temp = check_prime(a[i])
    if temp:
        check[a[i]] = 1
        ans += 1
print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
a.sort()
check = [True] * (a[-1] + 1)
cnt = Counter(a)

for i in range(n):
    if check[a[i]] == False:continue
    for j in range(a[i], a[-1] + 1, a[i]):
        if j == a[i]:continue
        check[j] = False

ans = 0
for i in range(n):
    if check[a[i]] and cnt[a[i]] == 1:ans += 1

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

n = int(input())
result=1
a = list(map(int,input().split()))
for i in a:
    result*=i
    
if 0 in a:
    print(0) 
    
elif result > 1000000000000000000:
    print(-1)

else:
    print(result)

### FIXED CODE ###

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

import math
N, K = map(int, input().split())
h = list(map(int, input().split()))

S = [0] * N
S[0] = 0

for i in range(1, N):
    value = math.inf
    for step in range(1, K + 1):
        # print("i, k:", i, k)
        if i - step < 0:
            break
        value = min(value, S[i - step] + abs(h[i] - h[i - step]))
        #print("value", value)
    S[i] = value
    # print(S)
# print(S)
print(S[N - 1])


### FIXED CODE ###

N,K=map(int,input().split())
h=list(map(int,input().split()))
dp=[0]*(N)
dp[1]=abs(h[0]-h[1])
for i in range(2,N):
    dp[i]=min(dp[j]+abs(h[j]-h[i]) for j in range(max(0,i-K),i))
print(dp[N-1])