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

# -*- coding: utf-8 -*-
from itertools import combinations

def inpl(): return list(map(int, input().split()))

N = int(input())
res = 0
exist = True
A = []

for _ in range(N):
    A.append(inpl())

for i, j in combinations(range(N), 2):
    vervose = False

    if not exist:
        break

    for k in range(N):
        if i == k or j == k:
            pass
        else:
            if A[i][j] < A[i][k] + A[k][j]:
                pass
            elif A[i][j] == A[i][k] + A[k][j]:
                vervose = True
            else:
                exist = False
                break
    if vervose:
        pass
    else:
        res += A[i][j]

if exist:
    print(res)
else:
    print(-1)

### FIXED CODE ###

# -*- coding: utf-8 -*-
from itertools import combinations

def inpl(): return tuple(map(int, input().split()))

N = int(input())
res = 0
exist = True
A = []

for _ in range(N):
    A.append(inpl())

for i, j in combinations(range(N), 2):
    vervose = False

    for k in range(N):
        if A[i][j] > A[i][k] + A[k][j]:
            exist = False
            break
    
    if not exist:
        break
    
    for k in range(N):
        if i == k or j == k:
            pass
        elif A[i][j] == A[i][k] + A[k][j]:
            vervose = True
            break
        
    if not vervose:
        res += A[i][j]
if exist:
    print(res)
else:
    print(-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 ###

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

a,b=map(int, input().split())
ans=1
for i in range(a, b+1):
  ans = ans*i
if (ans==0):
  print('Zero')
elif ans>0:
  print('Positive')
else:
  print('Negative')

### FIXED CODE ###

a,b=map(int, input().split())
ans=1
if a <= 0 and b >= 0:
  print('Zero')
  exit(0)
if a>0 and b > 0:
  print('Positive')
  exit(0)
if a <0 and b<0:
  d=abs(b-a)+1
  if d %2==0:
    print('Positive')
    exit(0)
  else:
    print('Negative')
    exit(0)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = list()
for i in range(n):
	if i % 2 == 0:
		b.append(a[i])
	else:
		b.insert(0, a[i])
if n % 2 == 1:
	b = b[::-1]

for x in b:
	print(x, end=' ')
print()

### FIXED CODE ###

from collections import deque
d = deque()
n = int(input())
a = input().split()

for i in range(n):
	if i % 2 == n % 2:
		d.append(a[i])
	else:
		d.appendleft(a[i])

print(' '.join(d))
### BUGGY CODE ###

import copy
N,A,B= map(int,raw_input().split())
h=[input() for _ in range(N)]

high=max(h)
low=1

def enough(T):
	h2=copy.deepcopy(h)
	cnt=0
	for i in range(N):
		h2[i]-=T*B
		if h2[i]>0:
			if h2[i]%(A-B)==0:
				cnt+=h2[i]/(A-B)
			else:
				cnt+=h2[i]/(A-B)+1
	if cnt<=T:
		return True
	else:
		return False

ans=0
while low<=high:
	c= (low + high) / 2
	if enough(c):
		high=c-1
		ans=c
	else:
		low=c+1


print ans



### FIXED CODE ###

N,A,B= map(int,raw_input().split())
h=[input() for _ in range(N)]

high=max(h)
low=1

def enough(T):
	cnt=0
	for i in h:
		i-=T*B
		if i>0:
			if i%(A-B)==0:
				cnt+=i/(A-B)
			else:
				cnt+=i/(A-B)+1
	if cnt<=T:
		return True
	else:
		return False

ans=0
while low<=high:
	c= (low + high) / 2
	if enough(c):
		high=c-1
		ans=c
	else:
		low=c+1


print ans
### BUGGY CODE ###

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

sums = [0 for _ in range(N)]
remainders = [0 for _ in range(M)]

ans = 0

for i in range(N):
    if i == 0:
        sums[0] = A[i] % M
        t = sums[0]
    else:
        t = (A[i] % M + sums[i-1]) % M
        sums[i] = t
    remainders[t] += 1
    ans += remainders[t] if t == 0 else remainders[t] - 1

print(ans)


### FIXED CODE ###

import collections
n, m = map(int, input().split())
A = [int(i) for i in input().split()]

R = [0]
a = 0
for i in range(n):
    a += A[i]
    a %= m
    R.append(a)


def nc2(n):
    return n*(n-1)//2


c = collections.Counter(R)
ans = 0
for r in set(R):
    ans += nc2(c[r])
print(ans)
### BUGGY CODE ###

def rewrite_count(vi_list):
    if len(set(vi_list)) != 1:
        vi_count_list = sorted([(i, vi_list.count(i)) for i in set(vi_list)], key=lambda x: x[1])
        return vi_count_list[-1][0], len(vi_list) - vi_count_list[-1][1], len(vi_list) - vi_count_list[-2][1]
    else:
        return vi_list, 0, "null"

N = int(input())
v_list = input().split()

if len(set(v_list)) == 1:
    print(len(v_list) // 2)
    exit()

v1_list = [v_list[i] for i in range(0, len(v_list), 2)]
v2_list = [v_list[i] for i in range(1, len(v_list), 2)]
max_v1, max_value_v1, second_value_v1 = rewrite_count(v1_list)
max_v2, max_value_v2, second_value_v2 = rewrite_count(v2_list)

if max_v1 != max_v2:
    ans = max_value_v1 + max_value_v2
elif max_value_v1 > max_value_v2:
    ans = max_value_v2 + second_value_v1
else:
    ans = max_value_v1 + second_value_v2
print(ans)

### FIXED CODE ###

from collections import *

N = int(input())
v_list = input().split()

if len(set(v_list)) == 1:
    print(len(v_list) // 2)
    exit()

v1_list = v_list[::2]
v2_list = v_list[1::2]

v1_count_list = Counter(v1_list).most_common()
v2_count_list = Counter(v2_list).most_common()

if v1_count_list[0][0] != v2_count_list[0][0]:
    print(len(v_list) - v1_count_list[0][1] - v2_count_list[0][1])
else:
    countor1 = len(v_list) - v1_count_list[1][1] - v2_count_list[0][1]
    countor2 = len(v_list) - v1_count_list[0][1] - v2_count_list[1][1]
    print(min(countor1, countor2))
### BUGGY CODE ###

s = input()
ans = [0 for i in range(len(s))]
RL_ind = []

for i in range(len(s)-2):
    if s[i:i+2] == "RL":
        RL_ind.append(i)
if s[-2:] == "RL":
    RL_ind.append(len(s)-2)

for i in range(len(s)):
    if s[i] == "R":
        ans_R = [j for j in RL_ind if j >= i]
        if (min(ans_R)-i)%2 == 0:
            ans[min(ans_R)] += 1
        else:
            ans[min(ans_R)+1] += 1
    else:
        ans_L = [j for j in RL_ind if j < i]
        if (max(ans_L)-i)%2 == 0:
            ans[max(ans_L)] += 1
        else:
            ans[max(ans_L)+1] += 1

print(*ans)

### FIXED CODE ###

S = list(input())

ans = [0 for _ in range(len(S))]

s_flag = 0
cnt = 0
for i, s in enumerate(S):
    if s == "R":
        s_flag = 1
        cnt += 1
    else:
        if s_flag and s == "L":
            ans[i] += cnt//2 
            ans[i-1] += cnt//2 + cnt%2
            cnt = 0
            s_flag = 0
# print(ans)

S.reverse()
ans.reverse()
# print(S)
# print(ans)

l_flag = 0
cnt = 0
for i, s in enumerate(S):
    if s == "L":
        l_flag = 1
        cnt += 1
    else:
        if l_flag and s == "R":
            ans[i] += cnt//2 
            ans[i-1] += cnt//2 + cnt%2
            cnt = 0
            l_flag = 0
    # print(ans)
ans.reverse()
print(*ans)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline

    n = int(input())
    a = list(map(int, input().split()))
    A = []
    A_append = A.append
    cnt = 0

    for i in range(n-1):
        A_append((a[i]))
        x = sum(A)
        if x > 0 and x + a[i+1] > 0:
            y = -(x + a[i+1] + 1)
            cnt -= y
            a[i+1] += y

        elif x < 0 and x + a[i+1] < 0:
            y = -(x - a[i+1]+ 1)
            cnt += y
            a[i+1] += y

    if sum(a) == 0:
        cnt += 1

    print(cnt)

if __name__ == '__main__':
    main()

### FIXED CODE ###

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

def Chk(a, pos):
    cnt = 0
    tmp = 0

    for a in A:
        tmp += a

        if pos and tmp < 1:
            cnt += 1 - tmp
            tmp = 1
        elif not pos and tmp > -1:
            cnt += 1 + tmp
            tmp = -1

        pos = not pos
    return cnt

print(min(Chk(A, True), Chk(A, False)))
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
ans = 1
for i in range(N):
    ans *= a[i]
    if ans == 0:
        break
if ans > 10 ** 18:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

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

d = int(input())
C = list(map(int, input().split()))
S = list(list(map(int, input().split())) for _ in range(d))

out = []

def compute(task_list):
    res = 0
    last = [0] * 26
    for i in range(len(task_list)):
        last[task_list[i]] = i

        for j in range(26):
            res -= C[j] * (i - last[j])

        res += S[i][task_list[i]]   
    return res

for _ in range(d):
    score = 0
    best_type = 0
    for i in range(26):
        out.append(i)
        tmp = compute(out)

        if tmp > score:
            score = tmp
            best_type = i
        
        out.pop()
    out.append(best_type)

print(*out, sep = '\n')


### FIXED CODE ###

d = int(input())
c = list(map(int, input().split()))
s = list(map(int, input().split()) for _ in range(d))

import random
for i in range(d):
    print(int(random.uniform(1, 26)))
### BUGGY CODE ###

A,B,K=map(int,input().split())
for i in range(K):
    if A>=1:
        A-=1
    elif B>=1:
        B-=1
    elif A==0 and B==0:
        break
print(A,B)

### FIXED CODE ###

A,B,K=map(int,input().split())
if A>=K:
    print(A-K,B)
elif A+B>=K:
    print(0,B-(K-A))
else:
    print(0,0)
### BUGGY CODE ###

#coding=UTF-8

def turn_check(zikan,direct,around):
    nokori_naka=zikan
    for idx in range(0,N,1):
        rem_hp=kirei_HP[idx]-around*zikan
        if rem_hp > 0:
            myon= rem_hp//(direct-around) + (0 if rem_hp%(direct-around)==0 else 1)
        
            nokori_naka=nokori_naka-myon
            if nokori_naka < 0:
                return False
        else: #以降も周辺攻撃のみで倒せる
            return True

    return True


mozir=input()
hyo=mozir.split(' ')
N=int(hyo[0])
A=int(hyo[1])
B=int(hyo[2])

HP=[]
for idx in range(0,N,1):
    HP.append(int(input()))

kirei_HP=sorted(HP,reverse=True)
kagen=kirei_HP[0]// B + 1
tansaku=kagen//2
while True:
    if turn_check(tansaku,A,B):
        kagen=tansaku
        tansaku=kagen//2
    else:
        if tansaku + 1 == kagen: #丁度境目を見付けたら
            break
        else:
            tansaku=(tansaku+kagen)//2

print(kagen)


### FIXED CODE ###

#coding=UTF-8
myon_chache={}
def turn_check(zikan,direct,around):
    nokori_naka=zikan
    for idx in range(0,N,1):
        rem_hp=kirei_HP[idx]-around*zikan
        if rem_hp > 0:
            if rem_hp in myon_chache:
                myon=myon_chache[rem_hp]
            else:
                myon= rem_hp//(direct-around) + (0 if rem_hp%(direct-around)==0 else 1)
                myon_chache[rem_hp]=myon
        
            nokori_naka=nokori_naka-myon
            if nokori_naka < 0:
                return False
        else: #以降も周辺攻撃のみで倒せる
            return True

    return True


mozir=input()
hyo=mozir.split(' ')
N=int(hyo[0])
A=int(hyo[1])
B=int(hyo[2])

HP=[]
for idx in range(0,N,1):
    HP.append(int(input()))

kirei_HP=sorted(HP,reverse=True)
dmg_mean= B
kagen=kirei_HP[0]// dmg_mean + 1
tansaku=kagen//2
ite=0
dame_jogen=0
while True:
    ite=ite+1
    if turn_check(tansaku,A,B):
        kagen=tansaku
        tansaku=(kagen+dame_jogen)//2
    else:
        if tansaku + 1 == kagen: #丁度境目を見付けたら
            break
        else:
            dame_jogen=tansaku
            tansaku=(tansaku+kagen)//2

#print(ite)
print(kagen)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
Flag = True
for i in range(n):
    for j in range(i+1,n):
        if a[i] == a[j]:
            Flag = False
if Flag:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

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

b = set(a)
Flag = (len(a) == len(b))
if Flag:
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

#!/usr/bin/env python3
N = int(input())

print(0, flush=True)
w1 = input()
if w1 == 'Vacant':
    exit()

l, r = 0, N - 1
while r - l > 1:
    m = (l + r) // 2
    print(m, flush=True)
    w2 = input()
    if w2 == 'Vacant':
        break
    if w1 == w2:
        l, r = (l, m) if (m - l) & 1 else (m, r)
    else:
        l, r = (m, r) if (m - l) & 1 else (l, m)
    w1 = w2


### FIXED CODE ###

#!/usr/bin/env python3
N = int(input())

print(0, flush=True)
w0 = input()
if w0 == 'Vacant':
    exit()

l, r = 0, N
while True:
    m = (l + r) // 2
    print(m, flush=True)
    w1 = input()
    if w1 == 'Vacant':
        break
    if m % 2 == (w0 != w1):
        l = m
    else:
        r = m
### BUGGY CODE ###

n=int(input())
a=[0]*n
for i in range(n):
    a[i]=int(input())
ans=0
for i in range(n):
    if a.count(a[i])%2!=0 and a[i] not in a[:i]:
        ans +=1
print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline
n=int(input())
a=[int(input()) for _ in range(n)]
a.sort()
h=a[0]
ans=1
for i in a[1:]:
    if i!=h:
        ans+=1
        h=i
    else:
        ans-=1
        h=pow(10,10)    
print(ans)
### BUGGY CODE ###

from math import gcd

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

lcm = 1
for a in A:
    lcm = lcm * a // gcd(lcm, a)


ans = 0
for a in A:
    ans += lcm // a
    if ans >= MOD:
        ans %= MOD

print(ans)

### FIXED CODE ###

from fractions import gcd


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


    l = 1

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


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

    print(ans)


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

import sys
from collections import deque
import copy


readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prl = lambda x: print(*x ,sep='\n')

def bfs(start,ex_kyori):
    tansaku = deque()
    tansaku.append(start)
    visited = {i:set() for i in range(h)}
    kyori = copy.deepcopy(ex_kyori)
    while tansaku:
        pre_y,pre_x = tansaku.popleft()
        if pre_x in visited[pre_y]:
            continue
        for i in range(pre_x-1,pre_x+2,2):
            if 0 <= i <= w-1 and tizu[pre_y][i] == '.':
                tansaku.append([pre_y,i])
                kyori[pre_y][i] = min(kyori[pre_y][i],kyori[pre_y][pre_x]+1)
        for j in range(pre_y-1,pre_y+2,2):
            if 0 <= j <= h-1 and tizu[j][pre_x] == '.':
                tansaku.append([j,pre_x])
                kyori[j][pre_x] = min(kyori[j][pre_x],kyori[pre_y][pre_x]+1)
        visited[pre_y].add(pre_x)
    return kyori

h,w = nm()
tizu = []
sharp = []
saitan = [[10**10]*w for _ in range(h)]
for i in range(h):
    temp = list(input())
    s_temp = [[i,j] for j in range(w)  if temp[j] == '#' ]
    tizu.append(temp)
    sharp += s_temp
for i,j in sharp:
    saitan[i][j] = 0 
for i in sharp:
    saitan = bfs(i,saitan)
print(max(max(i) for i in saitan))

### FIXED CODE ###

import sys
from collections import deque



readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prl = lambda x: print(*x ,sep='\n')

def bfs(start):
    tansaku = deque(start)
    visited = {i:set() for i in range(h)}
    res = 0
    black = len(start)
    while black != h*w:
        for _ in range(len(tansaku)):
            pre_y,pre_x = tansaku.popleft()
            if pre_x in visited[pre_y]:
                continue
            for i in range(pre_x-1,pre_x+2,2):
                if 0 <= i <= w-1 and tizu[pre_y][i] == '.':
                    tansaku.append([pre_y,i])
                    tizu[pre_y][i] = '#'
            for j in range(pre_y-1,pre_y+2,2):
                if 0 <= j <= h-1 and tizu[j][pre_x] == '.':
                    tansaku.append([j,pre_x])
                    tizu[j][pre_x] = '#'
            visited[pre_y].add(pre_x)
        black += len(tansaku)
        res += 1
    return res

h,w = nm()
tizu = []
sharp = []
for i in range(h):
    temp = list(input())
    s_temp = [[i,j] for j in range(w)  if temp[j] == '#' ]
    tizu.append(temp)
    sharp += s_temp
ans = bfs(sharp)
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""


"""


def chmin(i, j):
    a, b = dp[i+j], dp[i]+abs(h[i]-h[i+j])
    if a > b:
        dp[i+j] = b


n, k = map(int, (input().split()))
h = list(input().split())
h = [int(i) for i in h]
dp = [10**10]*n
dp[0] = 0
for i in range(0, n):
    for j in range(1, k+1):
        if i+j < n:
            chmin(i, j)
print(dp[n-1])

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
B - Frog 2
https://atcoder.jp/contests/dp/tasks/dp_b

"""
import sys
from sys import stdin


def solve(ashiba, N, K):
    dp = [float('inf')] * N
    dp[0] = 0
    for i in range(1, len(ashiba)):
        paths = [dp[j]+abs(ashiba[j]-ashiba[i]) for j in range(max(0, i-K), i)]
        dp[i] = min(paths)
    return dp[-1]


def main(args):
    N, K = map(int, input().split())
    ashiba = [int(i) for i in input().split()]
    ans = solve(ashiba, N, K)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])
### BUGGY CODE ###

S = input()
n = 0
import re
re.sub('BB+',"BB",S)
re.sub("WW+",'WW',S)
if 'BWBWBW' in S:
    n += 6*S.count('BWBWBW')
    S = S.replace('BWBWBW','WB')
while 'BW' in S:
    n += S.count('BW')
    S = S.replace('BW','WB')
print(n)

### FIXED CODE ###

S = input()
n = 0
k = 0
m = len(S)
for i in range(m):
    if S[i] == 'B':
        n += m - (i+1) -k
        k += 1
print(n)
### BUGGY CODE ###

L = 1000000000000000000
r = 1
n = input()
for a in map(int, input().split()):
    r *= a
if r > L: print(-1)
else: print(r)

### FIXED CODE ###

L = 1000000000000000000
r = 1
n = input()
A = list(map(int, input().split()))
A = sorted(A)
if A[0] == 0:
    print(0)
else:
    p = True
    while len(A) > 0:
        b = A.pop()
        r *= b
        if r > L:
            print(-1)
            p = False
            break
    if p: print(r)
### BUGGY CODE ###

h,w,k=map(int,input().split())
p,n=10**9+7,h+w
x=k+k*(k+1)//2+k*(k-1)*(k+1)//3*h*w*pow(n*(n-1),p-2,p)
for i in range(n,n-k,-1):x=x*i%p
print(x)


### FIXED CODE ###

h,w,k=map(int,input().split())
p,n=10**9+7,h+w
x=k+k*(k+1)//2+k*(k-1)*(k+1)//3*h*w*pow(n*(n-1),p-2,p)
for i in range(n,n-k,-1):x=x*i%p
print(x)
### BUGGY CODE ###

# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H, W):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


H, W = read_ints()
A = read_map(H, W)


# print(A)

from itertools import product
import numpy as np

# 黒の座標
ey, ex = [], []
# 白の座標
start = []
for i, a in enumerate(A):
    for j, aa in enumerate(a):
        if aa == '#':
            ey.append(i)
            ex.append(j)
        else:
            start.append((i, j))


ey = np.array(ey)
ex = np.array(ex)


def mahattan(sy, sx, ey, ex):
    return np.abs(sy - ey) + np.abs(sx - ex)


ans = 0

for i, j in start:
    tmp = mahattan(i, j, ey, ex).min()
    ans = max(ans, tmp)

print(ans)


### FIXED CODE ###

# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H, W):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


H, W = read_ints()
A = read_map(H, W)

from itertools import product
from collections import deque


# 開始地点
start = []
for i, a in enumerate(A):
    for j, aa in enumerate(a):
        if aa == '#':
            start.append((i, j))


# 探索の準備
mvx = (1, 0, -1, 0)
mvy = (0, 1, 0, -1)
visited = [[False for _ in range(W)] for _ in range(H)]

n_white = W*H
que = deque([(si, sj, 0) for si, sj in start])

for si, sj in start:
    visited[si][sj] = True

# 幅優先探索
while que:
    y, x, cost = que.popleft()
    # 白マスの数の管理
    n_white -= 1
    if n_white == 0:
        ans = cost
        break

    for dy, dx in zip(mvy, mvx):
        y_new, x_new = y + dy, x + dx
        # 探索に含めない条件
        if not (-1 < y_new < H) or not (-1 < x_new < W):
            continue
        if visited[y_new][x_new]:
            continue

        # 探索に追加してあげる
        que.append((y_new, x_new, cost + 1))
        visited[y_new][x_new] = True


print(cost)
### BUGGY CODE ###


def main():
    n, k = map(int, input().split(" "))
    p = list(map(int, input().split(" ")))
    ans = []
    for i in range(n-k+1):
        x = p[i:i+k]
        if sum(ans) < sum(x):
            ans = x
    a=0
    for i in range(k):
        b=0
        for j in range(ans[i]):
            b += j+1
        a += b/ans[i]
    print(a)


if __name__ == "__main__":
    main()

### FIXED CODE ###


def main():
    n, k = map(int, input().split(" "))
    p = list(map(int, input().split(" ")))
    u = [0]
    v = []
    w = []
    for i in range(n):
        u.append(u[i]+p[i])
    for i in range(n-k+1):
        w.append(u[k+i]-u[i])
    x = w.index(max(w))
    for i in range(k):
        v.append(p[x+i])
    a=0
    for i in range(k):
        a += 1+0.5*(v[i]-1)
    print(a)

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

import itertools, fractions
A, B = map(int, input().split())
cd_list = []
if A >= B:
    for n in range(1, B+1):
        if A%n == 0 and B%n == 0:
            cd_list.append(n)
else:
    for n in range(1, A+1):
        if A%n == 0 and B%n == 0:
            cd_list.append(n)
prime_list = [1]
for i in range(1, len(cd_list)):
        res = 0
        for n in cd_list[:i]:
            if fractions.gcd(cd_list[i], n) == 1:
                res += 1
        if res == len(cd_list[:i]):
                prime_list.append(cd_list[i])
print(len(prime_list))

### FIXED CODE ###

import fractions, math
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])
    if temp != 1:
        arr.append([temp, 1])
    if arr == []:
        arr.append([n, 2])
    return arr
A, B = map(int, input().split())
N = fractions.gcd(A, B)
prime_list = factorization(N)
if N == 1:
    print(1)
else:
    print(len(prime_list)+1)
### BUGGY CODE ###

K = int(input())
sum = 0
def gcd(x,y):
  r = x % y
  while r> 0:
    x = y
    y = r
    r = x%y
  return y
  
for a in range(K):
  for b in range(K):
    for c in range(K):
      sum += gcd(gcd(a+1,b+1),c+1)
print(sum)

### FIXED CODE ###

from functools import lru_cache
@lru_cache()
def gcd(x,y):
    r = x%y
    if r == 0:
        return y
    return gcd(y,r)

K = int(input())
Sum = 0

for i in range(1,K+1):
    Sum += i
    for j in range(i+1,K+1):
        Sum += 6*gcd(i,j)
        for k in range(j+1,K+1):
            Sum += 6*gcd(gcd(i,j),k)
print(Sum)