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

import sys
input = sys.stdin.readline
from numba import njit
import numpy


def read():
    N = int(input().strip())
    line = input().strip()
    P = numpy.fromstring(line, dtype=numpy.int32, sep=" ")
    return N, P


@njit
def dfs(N, Q, stay, y, x, q):
    for dy, dx in ((0, 1), (1, 0), (-1, 0), (0, -1)):
        ny, nx = y + dy, x + dx
        if 0 <= ny < N and 0 <= nx < N:
            if Q[ny, nx] > q:
                Q[ny, nx] = q
                dfs(N, Q, stay, ny, nx, q + stay[ny, nx])


@njit
def np_solve(N, P, INF=10**9):
    P -= 1
    Q = numpy.empty((N, N), dtype=numpy.int32)
    stay = numpy.ones((N, N), dtype=numpy.bool_)
    
    for i in range(N):
        for j in range(N):
            Q[i, j] = min([i, j, N-1-i, N-1-j])

    ans = 0
    for p in P:
        y, x = divmod(p, N)
        q = Q[y, x]
        stay[y, x] = 0
        ans += q
        dfs(N, Q, stay, y, x, q)
    return ans


if __name__ == '__main__':
    outputs = np_solve(*read())
    if outputs is not None:
        print("{}".format(outputs))


### FIXED CODE ###

import sys
input = sys.stdin.readline
from numba import njit
import numpy


def read():
    N = int(input().strip())
    line = input().strip()
    P = numpy.fromstring(line, dtype=numpy.int32, sep=" ")
    return N, P


@njit
def dfs(N, Q, stay, p, q):
    y, x = divmod(p, N)
    for dy, dx in ((0, 1), (1, 0), (-1, 0), (0, -1)):
        ny, nx = y + dy, x + dx
        if 0 <= ny < N and 0 <= nx < N:
            np = ny * N + nx
            if Q[np] > q:
                Q[np] = q
                dfs(N, Q, stay, np, q + stay[np])


@njit
def np_solve(N, P, INF=10**9):
    P -= 1
    Q = numpy.empty(N*N, dtype=numpy.int32)
    stay = numpy.ones(N*N, dtype=numpy.bool_)
    
    for i in range(N):
        for j in range(N):
            Q[i*N+j] = min([i, j, N-i-1, N-j-1])

    ans = 0
    for p in P:
        stay[p] = 0
        q = Q[p]
        ans += q
        dfs(N, Q, stay, p, q)
    return ans


if __name__ == '__main__':
    outputs = np_solve(*read())
    if outputs is not None:
        print("{}".format(outputs))
### BUGGY CODE ###

import math
import sys

N = int(sys.stdin.readline())
TA = []
for i in range(N):
    TA.append(list(map(int, sys.stdin.readline().split())))

current_T = 0
current_A = 0
for i in range(N):
    if i == 0:
        current_T = TA[i][0]
        current_A = TA[i][1]
        continue
    escape_flag = 0
    temp_T = math.floor(current_T / TA[i][0])
    temp_A = math.floor(current_A / TA[i][1])
    count = min([temp_T, temp_A])
    while escape_flag == 0:
        if TA[i][0] * count >= current_T and TA[i][1] * count >= current_A:
            escape_flag =1
        else:
            count += 1
    current_T = TA[i][0] * count
    current_A = TA[i][1] * count

print(current_T+ current_A)


### FIXED CODE ###

import math
import sys
from decimal import Decimal


N = int(sys.stdin.readline())
TA = []
for i in range(N):
    TA.append(list(map(int, sys.stdin.readline().split())))

current_T = 1
current_A = 1
for i in range(N):
    count = max(math.ceil(Decimal(current_T)/Decimal(TA[i][0])), math.ceil(Decimal(current_A)/Decimal(TA[i][1])))
    current_T = TA[i][0] * count
    current_A = TA[i][1] * count

print(current_T + current_A)
### BUGGY CODE ###

from collections import Counter


def solve(string):
    n, *a = map(int, string.split())
    table = [True] * (10**6 + 1)
    for _a in a:
        if table[_a]:
            for i in range(2 * _a, 10**6 + 1, _a):
                table[i] = False
    return str(sum(table[k] for k, v in Counter(a).items() if v == 1))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))


### FIXED CODE ###

import numpy as np
from collections import Counter


def solve(string):
    n, *a = map(int, string.split())
    table = np.array([True] * (10**6 + 1))
    for _a in a:
        if table[_a]:
            table[2*_a::_a]=False
    i = np.array([k for k,v in Counter(a).items() if v==1],dtype=np.int)
    return str(table[i].sum())


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))
### BUGGY CODE ###

A=input()
K=int(input())
A2=list(A.strip())
A2=set(A2)
A2=list(A2)
A2.sort()
Ans=A2[0]

def solve(st,s,k,li):
  an=set(s)
  lin=0
  while len(an)<=k:
    ch=False
    for i in range(len(st)):
      if st[i]==s:
        cnt=2
        while i+cnt<=len(st) or cnt<5:
          an.add(st[i:i+cnt])
          cnt+=1
    if len(an)<K:
      lin+=1
      s=li[lin]
      an.add(s)
      cnt=2
      
  an=list(an)
  an.sort()
  return an[k-1]

if K==1:
  print(Ans)
elif len(A) < 50:
  res=set()
  for i in range(len(A)):
    for j in range(i+1,len(A)+1):
      res.add(A[i:j])
  res=list(res)
  res.sort()
  print(res[K-1])
else:
  print(solve(A,Ans,K,A2))

### FIXED CODE ###

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

ans=set()
for i in range(len(s)):
  for j in range(i+1,i+K+1):
    if j<=len(s):
      ans.add(s[i:j])
ans=list(sorted(ans))
print(ans[K-1])
### BUGGY CODE ###

R,C,K = map(int, input().split())
a = [[0] * (C+1) for i in range(R+1)]
dp = [[[0] * (C+1) for i in range(R+1)] for j in range(4)]

for i in range(K):
  r,c,v = map(int, input().split())
  a[r-1][c-1] = v
  
for i in range(R):
  for j in range(C):
    for k in range(2,-1,-1):
      dp[k+1][i][j] = max(dp[k+1][i][j], dp[k][i][j] + a[i][j])
    for k in range(4):
      dp[0][i+1][j] = max(dp[0][i+1][j], dp[k][i][j])
      dp[k][i][j+1] = max(dp[k][i][j+1], dp[k][i][j])
ans = 0
for k in range(4):
  ans = max(ans, dp[k][R-1][C-1])
print(ans)
      
  

### FIXED CODE ###

R,C,K = map(int, input().split())
a = [[0] * (C+1) for i in range(R+1)]
dp = [[[0] * (C+1) for i in range(R+1)] for j in range(4)]
for i in range(K):
  r,c,v = map(int, input().split())
  a[r-1][c-1] = v

for i in range(R):
  for j in range(C):
    for k in range(2, -1, -1):
      dp[k+1][i][j] = max(dp[k+1][i][j], dp[k][i][j]+a[i][j])
    for k in range(4):
      dp[0][i+1][j] = max(dp[0][i+1][j], dp[k][i][j])
      dp[k][i][j+1] = max(dp[k][i][j+1], dp[k][i][j])

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

N, M = map(int, input().split())
if N >= M:
  print(0)
  exit()
  
X = list(map(int,input().split()))

X.sort()
dX,dX1 = [],[]
for i in range(M-1):
  dX.append(X[i+1]-X[i])
  dX1.append(X[i+1]-X[i])
seppoint = []

  
for i in range(N-1):
  dXmax = [j for j,v in enumerate(dX) if v == max(dX)]
  if len(dXmax) > 1: 
    sumdist0 = 2*10**5
    for k in dXmax:
      dXtmp = dX[:k] + dX[k+1:]
      sumdist1 = (sum(dXtmp))
      if sumdist0 > sumdist1:
        sumdist0 = sumdist1
        dX = dXtmp
        seppoint.append(k)
  else:
    dX = dX[:dXmax[0]] + dX[dXmax[0]+1:]
    seppoint.append(dXmax[0])
print(sum(dX))
#seppoint.sort()
#print(seppoint)
#for i in seppoint:
# dX1[i] = -1
#print(dX1)
#anslist = []
#tmpans = 0

#for i in range(len(dX1)):
#  if dX1[i] == -1:
#    anslist.append(tmpans)
#    tmpans = 0
#  else:
 #   tmpans += dX1[i]
 #   if i == len(dX1)-1:
 #     anslist.append(tmpans)
 #    tmpans = 0
 # print(anslist)
    
#print(max(anslist))

### FIXED CODE ###

N, M = map(int, input().split())
#if N >= M:
#  print(0)
#  exit()
  
X = list(map(int,input().split()))

X.sort()
diff = []

for i in range(1,M):
  diff.append(X[i]-X[i - 1])

diff.sort()

for i in range(N - 1):
  if len(diff) != 0:
    diff.pop()

print(sum(diff))
### BUGGY CODE ###

from functools import reduce
from operator import mul

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

num = reduce(mul, a[:k])
for i in range(k, n):
    num2 = num*a[i]//a[i-k]
    if num < num2:
        print('Yes')
    else:
        print('No')
    num = num2

### FIXED CODE ###

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

for i in range(k, n):
    if a[i]/a[i-k] > 1:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import networkx as nx
n,m=map(int,input().split())
s=[list(map(int,input().split())) for i in range(m)]
 
g=nx.Graph()
g.add_nodes_from([i for i in range(1,n+1)])
 
for x in s:
    g.add_edge(x[0],x[1])
di=nx.predecessor(g,source=1)
 
if len(di)!=n:
    print("No");exit()
print("Yes")
for x in range(2,n+1):
    print(di[x][0])

### FIXED CODE ###

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

ans_li = [-1]*n
queue=[0]
visited = [False]*n

while queue:
    x = queue.pop(0)
    for g in map_li[x]:
        if visited[g]==False:
            queue.append(g)
            if ans_li[g]==-1:
                ans_li[g]=x
                visited[g]=True 
if -1 in ans_li[1:]:
    print('No')
else:
    print('Yes')
    for ans in ans_li[1:]:
        print(ans+1)
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1] * (n + 1)
        self.rnk = [0] * (n + 1)

    def find_root(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]

    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1

    def isSameGroup(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def size(self, x):
        return -self.root[self.find_root(x)]


# adj: [[weight, u, v] * num_edge], V: number of vertices
def kruskal(adj, V):
    adj.sort()
    uf = UnionFind(V)
    ans = 0
    for edge in adj:
        weight, u, v = edge
        if not uf.isSameGroup(u, v):
            ans += weight
            uf.unite(u, v)
    return ans


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

x_list.sort()
y_list.sort()
adj = []
for i in range(N-1):
    adj.append([x_list[i + 1][0] - x_list[i][0], x_list[i + 1][1], x_list[i][1]])
    adj.append([y_list[i + 1][0] - y_list[i][0], y_list[i + 1][1], y_list[i][1]])

print(kruskal(adj, 2 * (N - 1)))


### FIXED CODE ###

# 6199094

import array
import sys
input = sys.stdin.readline

class UnionFind():
    def __init__(self,n):
        self.parent = [-1 for _ in range(n)]

    def size(self,x):
        return -self.parent[self.find(x)]

    def find(self,x):
        if(self.parent[x]<0):
            return x
        else:
            self.parent[x]=self.find(self.parent[x])
            return self.parent[x]

    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return False
        if(self.size(x)<self.size(y)):
            self.parent[y]+=self.parent[x]
            self.parent[x]=y
        else:
            self.parent[x]+=self.parent[y]
            self.parent[y]=x
        return True

    def same(self,x,y):
        return self.find(x)==self.find(y)

def main():
    N = int(input())
    xli = []
    yli = []
    x_app = xli.append
    y_app = yli.append


    for i in range(N):
        x,y = (int(x) for x in input().split())
        x_app([x-1,i])
        y_app([y-1,i])
    xli.sort()
    yli.sort()

    edges = []
    edges_app = edges.append
    for i in range(N-1):
        edges_app((xli[i][1],xli[i+1][1],xli[i+1][0]-xli[i][0]))
        edges_app((yli[i][1],yli[i+1][1],yli[i+1][0]-yli[i][0]))


    edges.sort(key=lambda edge: edge[2])
    uf = UnionFind(N)
    weight = 0

    for edge in edges:
        if not uf.same(edge[0], edge[1]):
            uf.unite(edge[0], edge[1])
            weight+=edge[2]
    print(weight)

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

from queue import deque

h,w = map(int,input().split())
li = [input() for _ in range(h)]

inf = 10**10
dx = [1,0]
dy = [0,1]
que = deque()

#そのマスにたどり着くまでに色が変わった最小の回数を保存するリスト
flip_count = [[inf for i in range(w)]for j in range(h)]

if li[0][0] == "#":
    flip_count[0][0] = 1
else:
    flip_count[0][0] = 0

que.append([0,0])

while que:
    k = que.popleft()
    x = k[0]
    y = k[1]
    for i,j in zip(dx,dy):
        nx = x + i
        ny = y + j
        if nx >= w or ny >= h:
            continue
        que.append([nx,ny])
        if li[ny][nx] != li[y][x]:
            flip_count[ny][nx] = min(flip_count[ny][nx],flip_count[y][x]+1)
        else:
            flip_count[ny][nx] = min(flip_count[ny][nx],flip_count[y][x])

if li[-1][-1] == "#":
    flip_count[-1][-1] += 1

print(flip_count[-1][-1]//2)

### FIXED CODE ###

from queue import deque

h,w = map(int,input().split())
li = [input() for _ in range(h)]

inf = 10**10
dx = [1,0]
dy = [0,1]
que = deque()

#そのマスにたどり着くまでに色が変わった最小の回数を保存するリスト
flip_count = [[inf for i in range(w)]for j in range(h)]

if li[0][0] == "#":
    flip_count[0][0] = 1
else:
    flip_count[0][0] = 0

que.append([0,0])

while que:
    k = que.popleft()
    x = k[0]
    y = k[1]
    for i,j in zip(dx,dy):
        nx = x + i
        ny = y + j
        if nx >= w or ny >= h:
            continue
        if flip_count[ny][nx] == inf:
            que.append([nx,ny])
        if li[ny][nx] != li[y][x]:
            flip_count[ny][nx] = min(flip_count[ny][nx],flip_count[y][x]+1)
        else:
            flip_count[ny][nx] = min(flip_count[ny][nx],flip_count[y][x])

if li[-1][-1] == "#":
    flip_count[-1][-1] += 1

print(flip_count[-1][-1]//2)
### BUGGY CODE ###

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

### FIXED CODE ###

import collections
n = int(input())
a = list(map(int, input().split(' ')))
l, r = [], []
for i in range(n):
    l.append(i + a[i])
    r.append(i - a[i])
c = collections.Counter(r)
ans = 0
for i in l:
    ans += c.get(i, 0)
print(ans)
### BUGGY CODE ###

N, M, K = map(int, input().split())
friend = [[] for _ in range(N+1)]
block = [[] for _ in range(N+1)]

for i in range(M):
  A,B = map(int, input().split())
  friend[A].append(B)
  friend[B].append(A)

for i in range(K):
  C,D = map(int, input().split())
  block[C].append(D)
  block[D].append(C)
#print(friend)
#print(block)

import queue
grouping = [False]*(N+1)
#print(grouping)
grouping[0] = True
group = [0]*(N+1)
g_num = 0
g_cnt = []
for i in range(1,N+1):
  cnt = 0
  if grouping[i] == True:
    continue 
  group[i] = g_num
  grouping[i] = True
  q = queue.Queue()
  q.put(i)
  while not q.empty():
    #print('v:',visited)
    p = q.get()
    for f in friend[p]:
      #print(p,f)
      if grouping[f]==False:
        q.put(f)
        group[f]=g_num
        grouping[f] =True
        cnt += 1
  g_num += 1
  g_cnt.append(cnt)
  #print('g:',grouping)
ans = []
for i in range(1,N+1):
  c = g_cnt[group[i]]-len(friend[i])
  for b in block[i]:
    if group[b]==group[i]:
      c -= 1
  ans.append(c)
print(*ans)

### FIXED CODE ###

N, M, K = map(int, input().split())
friend = [[] for _ in range(N+1)]
block = [[] for _ in range(N+1)]

for i in range(M):
  A,B = map(int, input().split())
  friend[A].append(B)
  friend[B].append(A)

for i in range(K):
  C,D = map(int, input().split())
  block[C].append(D)
  block[D].append(C)
#print(friend)
#print(block)

#import queue
grouping = [False]*(N+1)
#print(grouping)
grouping[0] = True
group = [0]*(N+1)
g_num = 0
g_cnt = []
for i in range(1,N+1):
  cnt = 0
  if grouping[i] == True:
    continue 
  group[i] = g_num
  grouping[i] = True
  #q = queue.Queue()
  #q.put(i)
  stack = [i]
  #while not q.empty():
  while len(stack)>0:
    #print('v:',visited)
    #p = q.get()
    p = stack.pop()
    for f in friend[p]:
      #print(p,f)
      if grouping[f]==False:
        #q.put(f)
        stack.append(f)
        group[f]=g_num
        grouping[f] =True
        cnt += 1
  g_num += 1
  g_cnt.append(cnt)
  #print('g:',grouping)
ans = []
for i in range(1,N+1):
  c = g_cnt[group[i]]-len(friend[i])
  for b in block[i]:
    if group[b]==group[i]:
      c -= 1
  ans.append(c)
print(*ans)
### BUGGY CODE ###

n,m = map(int,input().split())
a = []
for i in range(m):
    A = int(input())
    a.append(A)
mod = 1000000007
dp = [0] * (n+1)
dp[0] = 1#0段目へ行く移動方法は1通りしかない
if 1 not in a:#もし階段がぶっ壊れてるリストに1段目が入っていないならば1段目へ行く移動方法は1通り、そうでないなら0通り
    dp[1] = 1
else:
    dp[1] = 0
for i in range(2,n+1):#2段目から調べていく
    if i in a:#現在のi段目がぶっ壊れリストに含まれてるなら何もせず飛ばす
        continue
    dp[i] = dp[i-1] + dp[i-2]#フィボナッチで処理
    dp[i] %= mod#modで割っていく
print(dp[n])#n+1番目を出力する

### FIXED CODE ###

N, M = map(int, input().split())
a = set([int(input()) for _ in range(M)])
INF = 1000000007

dp = [0] * (N + 1)
dp[0] = 1
if 1 not in a:
	dp[1] = 1
else:
	dp[1] = 0
for i in range(2, N + 1):
	if i in a:
		continue
	dp[i] = dp[i - 1] + dp[i - 2]
	dp[i] %= INF

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

n = int(input())
l = []
for i in range(n):
    tmp = input().split()
    ope = tmp[0]
    if ope == "insert":
        m = tmp[1]
        l.insert(0,m)
    elif ope == "delete":
        m = tmp[1]
        if m in l:
            l.remove(m)
    elif ope == "deleteFirst":
        l.pop(0)
    elif ope == "deleteLast":
        l.pop()
print(*l)

### FIXED CODE ###

from collections import deque

n = int(input())
d = deque()
for i in range(n):
    tmp = input().split()
    ope = tmp[0]
    if ope == "insert":
        m = tmp[1]
        d.appendleft(m)
    elif ope == "delete":
        m = tmp[1]
        if m in d:
            d.remove(m)
    elif ope == "deleteFirst":
        d.popleft()
    elif ope == "deleteLast":
        d.pop()
print(*d)
### BUGGY CODE ###

from collections import deque
N,M = map(int, input().split())
if M == 0:
    print(-1)
    exit()
pqcs = [list(map(int, input().split())) for _ in range(M)]
c_max = max(list(map(lambda x: x[2],pqcs)))
node_num = (c_max+1)*N
Q = {0:deque([1])}
distance = {1:0}

#辺へ重み付け
edges = {}
for p,q,c in pqcs:
	edge = {}
	edge[c*10**6+q] = 0
	edge[p] = 0
	edges.setdefault(c*10**6+p, {})
	edges[c*10**6+p].update(edge)
	edge = {}
	edge[c*10**6+p] = 0
	edge[q] = 0
	edges.setdefault(c*10**6+q, {})
	edges[c*10**6+q].update(edge)
	edge = {}
	edge[c*10**6+p] = 1
	edges.setdefault(p, {})
	edges[p].update(edge)
	edge = {}
	edge[c*10**6+q] = 1
	edges.setdefault(q, {})
	edges[q].update(edge)

flag = False
while 1:
	for i in range(len(Q)):                            
		if not (Q[i]):
			continue
		flag = True
		target_min_ind = Q[i].popleft()
		target_node = edges[target_min_ind]
		break
	if not (flag):
		break

	for key, value in target_node.items():
		distance.setdefault(key, float('inf'))
		dist = distance[target_min_ind] + value
		if distance[key] > dist:
			distance[key] = dist
			Q.setdefault(dist, deque())
			Q[dist].append(key)
		if key == N:
			flag = False
	if not (flag):
		break

print(distance[N] if distance[N] != float('inf') else -1)
exit()

### FIXED CODE ###

from collections import deque
N, M = map(int, input().split())
F_C_of_S = [{} for i in range(N)]
#Companies of Station
C_of_S = {}

#def Union-find
parent = [-1]*M
def root(x):
	if (parent[x] < 0): return x
	else:
		parent[x] = y = root(parent[x])
		return y

def unite(x, y):
	px = root(x)
	py = root(y)
	if (px == py): return False
	if (parent[px] > parent[py]):
		px = root(y)
		py = root(x)
	parent[px] += parent[py]
	parent[py] = px
	return True


#Union-find
pqcs = []
for i in range(M):
	p, q, c = map(int, input().split())
	p -= 1; q -= 1;
	pqcs += [(p, q, c)]
	
	#The first
	if not c in F_C_of_S[p]: F_C_of_S[p][c] = i
	#else
	else: unite(F_C_of_S[p][c], i)
	C_of_S.setdefault(p, set()).add(c)
	
	#The first
	if not (c in F_C_of_S[q]):F_C_of_S[q][c] = i
	#else
	else: unite(F_C_of_S[q][c], i)
	C_of_S.setdefault(q, set()).add(c)

#stations of company
S_of_C = {}
for i in range(M):
	p, q, c = pqcs[i]
	c_set = S_of_C.setdefault(root(i), set())
	c_set.add(p)
	c_set.add(q)


Q = deque([(0, 0, 0)])
#cost to go to the stations from station_0
dist = [float('inf')]*N
dist[0] = 0

gdist = [float('inf')]*M

while Q:
	cost, v, flag = Q.popleft()
	
	if not (flag):#(flag == 0) then gdist_update
		if (dist[v] < cost) or (v not in C_of_S):
			continue
		for l in F_C_of_S[v].values():
			l = root(l)
			if (cost < gdist[l]):
				gdist[l] = cost
				Q.appendleft((cost, l, 1))
	
	else:#(flag == 1) then dist_update
		if (gdist[v] < cost) or (v not in S_of_C):
			continue
		for s in S_of_C[v]:
			if (cost+1 < dist[s]):
				dist[s] = cost+1
				Q.append((cost+1, s, 0))

print(dist[N - 1] if dist[N - 1] < float('inf') else -1)
### BUGGY CODE ###

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

A = collections.Counter(A)
cnt = 0
n = len(A.keys())
for _ in range(n):
    if len(A.keys()) <= K:
        break
    k, v = min(A.items(), key=lambda x: x[1])
    cnt += v
    del A[k]
    
print(cnt)

### FIXED CODE ###

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

A = collections.Counter(A)
A = sorted(A.items(), key=lambda x:x[1])
cnt = A[:len(A)-K]

ans = []
for c in cnt:
    ans.append(c[1])
    
print(sum(ans))
### BUGGY CODE ###

N=int(input())
a = 1

while N!=0:
  a = N*a
  N =N-1
print(a%(10**9+7))
  
  

### FIXED CODE ###

import math
N=int(input())
print(math.factorial(N)%(10**9+7))
### BUGGY CODE ###

N,K=list(map(int,input().split()))
old_N=N+1
while True:
  if old_N<=N:
    print(old_N)
    break
  old_N=N
  N=abs(N-K)

### FIXED CODE ###

N,K=list(map(int,input().split()))
n=N%K
old_n=K+1
while True:
  if old_n<=n:
    print(old_n)
    break
  old_n=n
  n=abs(n-K)
### BUGGY CODE ###

N = int(input())
S = input()
count = 0

for i in range(1000):
    pin = ("00" + str(i))[-3:]

    j = 0
    for num in S:
        if pin[j] == num:
            j += 1
        if j == 3:
            count += 1
            break

print(count)


### FIXED CODE ###

N = int(input())
S = input()
count = 0

for i in range(1000):
    pin = ("00" + str(i))[-3:]

    j = 0
    for num in S:
        if pin[j] == num:
            j += 1
        if j == 3:
            count += 1
            break

print(count)
### BUGGY CODE ###

# def to_2(num):
#     ret = []
#     while (num != 0):
#         if num % 2 == 1:
#             ret.append(True)
#         else:
#             ret.append(False)
#         num = num // 2
#     return np.array(ret)

# def()

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

# 全探索
from itertools import combinations
A_2 = [bin(a) for a in A]

kouho = [sum(A[idx:(idx2+1)]) for idx, idx2 in combinations(range(0, N), 2)]


ma = 0
for A_sub in combinations(kouho, K):
    bina = A_sub[0]
    # print(bina)
    for i in range(1, K):
        bina = bina & A_sub[i]
    if bina > ma:
        ma = bina

print(ma)

### FIXED CODE ###

# https://atcoder.jp/contests/dwacon5th-prelims/tasks/dwacon5th_prelims_b
# 解説見てしまった
# N≤1000の性質をうまく使う必要はない。O(N^2)で全部書き出せばいい。完全に引っ掛け。
# 答えの仮定、bitごとに見る、上位桁からのgreedyらへんがキーワード

from itertools import combinations
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = [sum(A[s:t]) for s, t in combinations(range(N + 1), 2)]

l = max(B).bit_length()  # 何桁扱えば十分か？
x = 0  # 初期値
for i in range(l, -1, -1):  # 上位桁からgreedyに決定
    # 候補のうち i bit目=1がK個以上あれば答えに計上できる
    x_tmp = x + (1 << i)
    if sum((x_tmp & b) == x_tmp for b in B) >= K:  # 確定した桁+i桁を1としたときに答えになり得るか？
        x = x_tmp
print(x)
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
v=sum(a)
for i in range(n-1):
    if k<a[i]+a[i+1]:
        while k<a[i]+a[i+1]:
            a[i+1]-=1
print(v-sum(a))

### FIXED CODE ###

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