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

l = input().split(" ")
w = int(l[0])
h = int(l[1])
n = int(l[2])

array = [[0 for i in range(h)] for j in range(w)]

for i in range(n):
	l = input().split(" ")
	x = int(l[0]) - 1
	y = int(l[1]) - 1
	for i in range(3):
		for j in range(3):
			if x+j-1 >=0 and x+j-1<w and y+i-1 >=0 and y+i-1<h:
				array[x+j-1][y+i-1] += 1

ans = [0 for i in range(10)]

for i in range(h-2):
	for j in range(w-2):
		ans[array[j+1][i+1]] += 1

for a in ans:
	print(a)

### FIXED CODE ###

"""
l = input().split(" ")
w = int(l[0])
h = int(l[1])
n = int(l[2])

array = [[0 for i in range(h)] for j in range(w)]

for i in range(n):
	l = input().split(" ")
	x = int(l[0]) - 1
	y = int(l[1]) - 1
	for i in range(3):
		for j in range(3):
			if x+j-1 >=0 and x+j-1<w and y+i-1 >=0 and y+i-1<h:
				array[x+j-1][y+i-1] += 1

ans = [0 for i in range(10)]

for i in range(h-2):
	for j in range(w-2):
		ans[array[j+1][i+1]] += 1

for a in ans:
	print(a)

"""

l = input().split(" ")
w = int(l[0])
h = int(l[1])
n = int(l[2])

array = dict()

for i in range(n):
	l = input().split(" ")
	x = int(l[0])
	y = int(l[1])
	for i in range(3):
		if y-i < 1 or y-i > h-2:
			continue
		for j in range(3):
			if x-j < 1 or x-j > w-2:
				continue
			if (x-j, y-i) in array:
				array[(x-j, y-i)] +=1
			else:
				array[(x-j, y-i)] = 1

ans = [0] * 10
ans[0] = (h-2) * (w-2)
 
for i in array:
    ans[array[i]] += 1
    ans[0] -= 1

for i in range(10):
    print(ans[i])
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
mod=10**9+7
ans=0
for i in range(60):
  c=0
  for j in A:
    if j>>i&1:
      c+=1
  ans+=pow(2,i,mod)*c*(N-c)
  ans%=mod
print(ans)

### FIXED CODE ###

def main():
  N=int(input())
  A=list(map(int,input().split()))
  mod=10**9+7
  ans=0
  for i in range(60):
    c=0
    for j in A:
      if j>>i&1:
        c+=1
    ans+=pow(2,i,mod)*c*(N-c)
    ans%=mod
  print(ans)
if __name__=='__main__':
  main()
### BUGGY CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))
ansmax = 0
for i in range(N-K+1):
  ans = 0
  for j in range(K):
    ans += (p[i+j]+1)/2
  if(ansmax < ans):
    ansmax = ans
print(ansmax)

### FIXED CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))
ansmax = 0
ans = 0
for j in range(K):
  ans += (p[j]+1)/2
if(ansmax < ans):
  ansmax = ans
for i in range(N-K):
  ans =  ans - (p[i]+1)/2 + (p[i+K]+1)/2
  if(ansmax < ans):
    ansmax = ans
print(ansmax)
### BUGGY CODE ###

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

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

min_a = min(a)

bc = []
for _ in range(m):
    b, c = (int(x) for x in input().split())
    bc.append([b,c])

bc = sorted(bc, key=lambda x: -x[1])

memo = []

limit = 0

for i in range(m):
    a = a + [bc[i][1]]*bc[i][0]
    limit += bc[i][0]
    if limit >= n or min_a >= bc[i][1]:
        break

a.sort(reverse=True)

ans = 0

for i in range(n):
    ans += a[i]
print(ans)

### FIXED CODE ###

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

t = list(map(int,input().split()))
ab=[]
for _ in range(m):
    a, b = (int(x) for x in input().split())
    ab.append([a,b])

t.sort(reverse=True)
ab = sorted(ab, key=lambda x: -x[1])
count = 0
for i,j in ab:
    t += [j]*i
    count += i
    if n <= count:
        break

t.sort(reverse=True)
        
print(sum(t[:n]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
#N, K = (int(i) for i in input().split())
#B = [int(x) for x in input().split()]
#A = [[int(i) for i in input().split()] for i in range(N)]

divmemo = {}
def popcountdiv(n):
    if n in divmemo:
        return divmemo[n]
    res = n % (bin(n).count("1"))
    divmemo[n] = res
    return res

memo = {}
def f(n):
    if n == 0:
        return 0
    if n in memo:
        return memo[n]
    else:
        res = f(popcountdiv(n))
        memo[n] = res+1
        return 1 + res

N = int(input())
X = input()

for i in range(N):
    print(f(int(X[:i] + str((int(X[i])+1)%2)+ X[i+1:] , 2)))


### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
X = input()
Xint = int(X, 2)
Xcount = X.count("1")

"""
0010
1010 10(mod2) -> 0
i = n-1の時だけ +1
0011 -> 3 -> 1->0
0110 -> 6(mod2) -> 0
"""

if Xcount == 1:
    for i in range(N):
        if X[i] == "1":
            print(0)
        elif i == N-1:
            print(2)
        else:
            print(1)
    exit()

Modplus, Modminus = Xint%(Xcount+1), Xint%(Xcount-1)

def f(x):
    if x == 0:
        return 0
    return f(x%bin(x).count("1"))+1

for i in range(N):
    if X[i] == "1":
        print(1+f((Modminus-pow(2, N-1-i, Xcount-1))%(Xcount-1)))
    else:
        print(1+f((Modplus+pow(2, N-1-i, Xcount+1))%(Xcount+1)))
### BUGGY CODE ###

N = int(input())
lis = [sorted(set((str(i)))) for i in range(357, N+1)]
print(lis.count(['3', '5', '7']))

### FIXED CODE ###

from itertools import product

N = int(input())

count = 0
for i in range(2, len(str(N))):
  for p in set(product('753', repeat=i+1)):
    if int(''.join(p)) > N:
      continue
    if all(p.count(s) > 0 for s in '753'):
      count += 1

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

import sys

class E(object):
    def __init__(self, p = None, v = None, n = None):
        self.p = p
        self.v = v
        self.n = n

    def rem(self):
        if self.p is not None:
            self.p.n = self.n
        if self.n is not None:
            self.n.p = self.p

    def ins(self, ne):
        self.p = ne
        ne.n = self

    def prt(self):
        sys.stdout.write(self.v)
        if self.n is not None:
            sys.stdout.write(" ")
            self.n.prt()

fe = le = None

n = int(input().strip())

for _ in range(n):
    cmd = input()
    if cmd == "deleteFirst":
        if fe is not None:
            fe.rem()
            if fe.n is not None:
                fe = fe.n
            else:
                fe = le = None
    elif cmd == "deleteLast":
        if le is not None:
            le.rem()
            if le.p is not None:
                le = le.p
            else:
                fe = le = None
    elif cmd.startswith("insert "):
        _, v = cmd.split(" ")
        e = E(None, v, None)
        if fe is not None:
            fe.ins(e)
        fe = e
        if le is None:
            le = e
    elif cmd.startswith("delete "):
        _, v = cmd.split(" ")
        e = fe
        while e is not None:
            if e.v == v:
                e.rem()
                if fe == e:
                    fe = e.n
                if le == e:
                    le = e.p
                break
            e = e.n

    #print("F: {}, L: {}".format(fe.v if fe is not None else "None", le.v if le is not None else "None"))

if fe is not None:
    fe.prt()
print("")

### FIXED CODE ###

from collections import deque

q = deque()

n = int(input().strip())

for _ in range(n):
    cmd = input()
    if cmd == "deleteFirst":
        q.popleft()
    elif cmd == "deleteLast":
        q.pop()
    elif cmd.startswith("insert "):
        v = cmd[7:]
        q.appendleft(v)
    elif cmd.startswith("delete "):
        v = cmd[7:]
        try:
            q.remove(v)
        except ValueError:
            pass
print(" ".join(q))
### BUGGY CODE ###

import heapq
N,M=map(int,input().split())

ab=[]
for _ in range(N):
  ab.append(list(map(int,input().split())))

sal=0
poss=[]
for i in range(1,M+1):
  for j in range(N):
    if ab[j][0]==i:
      heapq.heappush(poss,-ab[j][1])
  if len(poss)>0:
    sal+=-heapq.heappop(poss)
    
print(sal)

### FIXED CODE ###

import heapq
N,M=map(int,input().split())

ab=[[] for _ in range(M)]
for i in range(N):
  b,a=map(int,input().split())
  if b<=M:
    ab[b-1].append(a)

sal=0
poss=[]
for i in range(1,M+1):
  for j in ab[i-1]:
    heapq.heappush(poss,-j)
  if len(poss)>0:
    sal+=-heapq.heappop(poss)
    
print(sal)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

S = list(map(int, list(input())))
#print(S)
mod = 2019
mod_list = [0]
#last = 0
ten = 1

for num in S[::-1]:
    yo = (num * ten + mod_list[-1]) % mod
    #print(yo)
    mod_list.append(yo)
    #last = yo
    ten *= 10 % mod

cnt = [0]*2019

for yo in mod_list:
    cnt[yo] += 1

ans = 0
for i in range(2019):
    ans += cnt[i] * (cnt[i]-1) // 2

print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

S = list(map(int, list(input())))
#print(S)
mod = 2019
mod_list = [0]
#last = 0
ten = 1

for num in S[::-1]:
    yo = (num * ten + mod_list[-1]) % mod
    #print(yo)
    mod_list.append(yo)
    #last = yo
    ten = (ten * 10) % mod

cnt = [0]*2019

for yo in mod_list:
    cnt[yo] += 1

ans = 0
for i in range(2019):
    ans += cnt[i] * (cnt[i]-1) // 2

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

N=int(input())
A=list(map(str,input().split()))
Q=int(input())
B=[list(map(str,input().split())) for i in range(Q)]
A=','.join(A)
for i in B:
    A=A.replace(str(i[0]),str(i[1]))
    print(sum(list(map(int,str(A).split(',')))))


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
Q=int(input())
B=[list(map(int,input().split())) for i in range(Q)]

dp=[0 for i in range(1,10**6)]
for i in A:
    dp[i]+=1
S=sum(A)
for i in B:
    S+=(i[1]-i[0])*dp[i[0]]
    print(S)
    dp[i[1]]+=dp[i[0]]
    dp[i[0]]=0
### BUGGY CODE ###

from collections import deque
H, W = list(map(int, input().split(' ')))
FIELD = list()
for _ in range(H):
    FIELD.append(input())
removal_cell_flag = [[1 if FIELD[h][w] == '.' else 0 for w in range(W)] for h in range(H)]
sh, sw = 0, 0  # start
gh, gw = H - 1, W - 1  # goal
# We can get the maximum score
# when we change colors of cells which are not on the shortest path.
frontier = deque()
ch, cw = sh, sw
frontier.append((ch, cw))
explored_flag = [[0 for _ in range(W)] for _ in range(H)]
parent_table = [[None for _ in range(W)] for _ in range(H)]
while len(frontier) > 0:
    ch, cw = frontier.popleft()  # current
    if ch == gh and cw == gw:  # reach goal
        break
    explored_flag[ch][cw] = 1
    for dh, dw in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        nh, nw = ch + dh, cw + dw  # next
        if (nh < 0) or (H - 1 < nh) or (nw < 0) or (W - 1 < nw):
            continue
        if FIELD[nh][nw] == '#':
            continue
        if explored_flag[nh][nw] == 1:
            continue
        parent_table[nh][nw] = (ch, cw)
        frontier.append((nh, nw))
if ch != gh and cw != gw:
    print(-1)
    exit(0)
while True:
    removal_cell_flag[ch][cw] = 0
    if parent_table[ch][cw] is None:
        break
    ch, cw = parent_table[ch][cw]
print(sum([sum(row) for row in removal_cell_flag]))

### FIXED CODE ###

from collections import deque
H, W = list(map(int, input().split(' ')))
FIELD = list()
for _ in range(H):
    FIELD.append(input())
WHITE_CELL_NUM = 0
for h in range(H):
    for w in range(W):
        if FIELD[h][w] == '.':
            WHITE_CELL_NUM += 1
sh, sw = 0, 0  # start
gh, gw = H - 1, W - 1  # goal
# We can get the maximum score
# when we change colors of cells which are not on the shortest path.
frontier = deque()
ch, cw = sh, sw
frontier.append((ch, cw))
steps = [[-1 for _ in range(W)] for _ in range(H)]
steps[ch][cw] = 0
while len(frontier) > 0:
    ch, cw = frontier.popleft()  # current
    if ch == gh and cw == gw:  # reach goal
        break
    for dh, dw in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        nh, nw = ch + dh, cw + dw  # next
        if (nh < 0) or (H - 1 < nh) or (nw < 0) or (W - 1 < nw):
            continue
        if FIELD[nh][nw] == '#':
            continue
        if steps[nh][nw] >= 0:
            continue
        steps[nh][nw] = steps[ch][cw] + 1
        frontier.append((nh, nw))
if ch != gh and cw != gw:
    print(-1)
    exit(0)
shortest_path_length = steps[gh][gw] + 1
print(WHITE_CELL_NUM - shortest_path_length)
### BUGGY CODE ###

N = input()
P = list(map(int, input().split()))
count = 1

for i in range(int(N)-1):
    if P[i+1]<=(min(P[:i+1])):
            count = count + 1
print(count)
            

### FIXED CODE ###

N = input()
P = list(map(int, input().split()))
count = 0

now_mini= 1<<20
for i in P:
    if i < now_mini:
        count = count + 1
        now_mini=i
print(count)
### BUGGY CODE ###

n,m=map(int,input().split())
a=[]
for i in range(m):
  a.append(int(input()))
b=[0 for x in range(n+1)]
b[0]=1
for i in range(1,n+1):
  if i not in a:
    b[i]+=b[i-1]
    if i>1:b[i]+=b[i-2]
  else:
    b[i]=0
 
 
print(b[n]%(10**9+7))

### FIXED CODE ###

n,m=map(int,input().split())
a=[]
a = set(int(input()) for _ in range(m))
#for i in range(m):
#  a.append(int(input()))
b=[0 for x in range(n+1)]
b[0]=1
for i in range(1,n+1):
  if i in a:
    continue
  x=b[i-1]
  if i>1:x+=b[i-2]
  b[i]=x
print(b[n]%(10**9+7))
### BUGGY CODE ###

N,M=map(int,input().split())
mod=10**9+7
dp=[0 for i in range(N+1)]
dp[0]=1
dp[-1]=0
A=[]
for i in range(M):
  A.append(int(input()))
#print(A)
for i in range(1,N+1):
  if dp[i-1]==0 and dp[i-2]==0:
    break
  elif i in A:
    continue
  else:
    dp[i]=(dp[i-1]+dp[i-2])%mod
print(dp[N]%mod)


### FIXED CODE ###

N,M=map(int,input().split())
mod=10**9+7
dp=[0]*(N+1)
dp[0]=1
dp[-1]=0
A=[]
for i in range(M):
  A.append(int(input()))
A=set(A)
#print(A)
for i in range(1,N+1):
  if dp[i-1]==0 and dp[i-2]==0:
    break
  elif i in A:
    continue
  else:
    dp[i]=(dp[i-1]+dp[i-2])%mod
print(dp[N]%mod)
### BUGGY CODE ###

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

while len(li)>1:
    li.sort()
    li[-1] = li[-1]%li[0]
    if li[-1] == 0:
        li.pop()
print(li[0])

### FIXED CODE ###

from fractions import gcd
from functools import reduce
n = int(input())
li = list(map(int,input().split()))
print(reduce(gcd,li))
### BUGGY CODE ###

import math

N, M = map(int, input().split())
A = [int(i) for i in input().split()]


def solve():
    sorted_list = A

    for index in range(0, M):
        sorted_list = sorted(sorted_list)
        sorted_list[-1] = math.floor(sorted_list[-1] / 2)

    return sum(sorted_list)


print(solve())


### FIXED CODE ###

import heapq

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


def solve():
    AA = [[-x, x] for x in A]

    heapq.heapify(AA)

    for i in range(M):
        x, y = heapq.heappop(AA)
        heapq.heappush(AA, [-(y//2), y//2])

    AAA = [x[1] for x in AA]
    return sum(AAA)


print(solve())
### BUGGY CODE ###

N,M = map(int,input().split())
AB, C = [], []
for _ in range(M):
    AB.append(tuple(int(i) for i in input().split()))
    C.append(sum(1<<(int(i)-1) for i in input().split()))

INF = 10**18

# dp[i]: 状態がbin(i)のときの費用の最小値
# bin(i)のj桁が1: j番目の宝箱を開けられる
dp = [INF] * (1<<N)

# 初期条件(全ての宝箱を開けられない)
dp[0] = 0

for i in range(1<<N):
    for (a, _), c in zip(AB,C):
        # 状態iで状態cにする鍵を買ったときの状態
        dp[i | c] = min(dp[i | c], dp[i] + a)

if dp[-1] == INF:
    ans = -1
else:
    ans = dp[-1]
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N,M = map(int,input().split())
AB = []
C = []
for _ in range(M):
    AB.append(tuple(int(i) for i in input().split()))
    C.append(sum(1<<(int(i)-1) for i in input().split()))

INF = 10**18
# dp[i]: 状態がbin(i)のときの費用の最小値
# bin(i)のj桁が1: j番目の宝箱を開けられる
# 1<<N == 2**N
dp = [INF] * (1<<N)

# 初期条件(全ての宝箱を開けられない)
dp[0] = 0

for i in range(1<<N):
    for (a,b),c in zip(AB,C):
        # 状態iで状態cにする鍵を買ったときの状態
        state = i | c
        dp[state] = min(dp[state], dp[i]+a)

answer = dp[-1]
if answer == INF:
    answer = -1
print(answer)
### BUGGY CODE ###

N = int(input())
list = []
for i in range(N):
	list.append(int(input()))
for i in range(N):
	if(list[i] == max(list)):
		list_max = sorted(list)
		print(list_max[-2])
	else:
		print(max(list))

### FIXED CODE ###

N = int(input())
list = [int(input()) for i in range(N)]
list_max = sorted(list)
max = max(list)
for i in range(N):
	if(list[i] == max):
		print(list_max[-2])
	else:
		print(max)
### BUGGY CODE ###

n,m = map(int, input().split())
keys = []
for i in range(m):
  l,r = map(int, input().split())
  keys.append([l,r])
cnt = 0
for key in range(1, n+1):
  for x, y in keys:
    if key < x or key > y:
      cnt -= 1
      break
  cnt += 1
print(cnt)

### FIXED CODE ###

n,m = map(int, input().split())
l_lst, r_lst = [], []
for i in range(m):
  l,r = map(int, input().split())
  l_lst.append(l)
  r_lst.append(r)
res = min(r_lst)-max(l_lst)+1
if res > 0:
  print(res)
else:
  print(0)
### BUGGY CODE ###

s=input()
t=input()

fl_i=0
fl_j=0

dp=[['']*len(t) for _ in range(len(s))]

for i in range(len(s)):
    for j in range(len(t)):
        if i==0 or j==0:
            if s[i]==t[j]:
                dp[i][j]=s[i]
                fl_i=1 if i==0 else 0
                fl_j=1 if j==0 else 0
            elif fl_i==1:
                dp[i][j]=dp[i][j-1]
            elif fl_j==1:
                dp[i][j]=dp[i-1][j]
        else:
            if s[i]==t[j]:
                dp[i][j]=dp[i-1][j-1]+s[i]
            elif len(dp[i][j-1])>len(dp[i-1][j]):
                dp[i][j]=dp[i][j-1]
            else:
                dp[i][j]=dp[i-1][j]

print(dp[len(s)-1][len(t)-1])


### FIXED CODE ###

s=input()
t=input()


result=''
dp=[[0]*len(t) for _ in range(len(s))]

for i in range(len(s)):
    for j in range(len(t)):
        if i==0:
            if s[i]==t[j]:
                dp[i][j]=1
            else:
                dp[i][j]=dp[i][j-1] if j>=1 else 0
        elif j==0:
            if s[i]==t[j]:
                dp[i][j]=1
            else:
                dp[i][j]=dp[i-1][j]
        else:
            if s[i]==t[j]:
                dp[i][j]=dp[i-1][j-1]+1
            else:
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])

i=len(s)-1
j=len(t)-1

L=dp[i][j]

while L>=1:
    if i==0 and dp[i][j]==1:
        result+=s[i]
        L-=1
    elif j==0 and dp[i][j]==1:
        result+=t[j]
        L-=1
    elif dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        result+=t[j]
        L-=1
        i-=1
        j-=1


print(result[::-1])
### BUGGY CODE ###

list_ = [0]
n, min_count = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
kind = 1
tmp = a[0]
for i in range(n):
    if(tmp != a[i]):
        kind += 1
        tmp = a[i]
        list_.append(0)
    list_[kind - 1] += 1
ans = 0
for i in range(kind - min_count):
    min_idx = list_.index(min(list_))
    ans += list_[min_idx]
    list_[min_idx] = 200001
print(ans)

### FIXED CODE ###

list_ = [0]
n, min_count = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
kind = 1
tmp = a[0]
for i in range(n):
    if(tmp != a[i]):
        kind += 1
        tmp = a[i]
        list_.append(0)
    list_[kind - 1] += 1
ans = 0
list_.sort()
idx = 0
for i in range(kind - min_count):
    ans += list_[idx]
    idx += 1
print(ans)
### BUGGY CODE ###

A,B,C,K = map(int,input().split())

count = K
score = 0

if(0 <= A-K):
    print(K)

else:
    while(0 < count):
        if(0 < A):
            score += 1
            count -=1
            A -=1
        else:
            if(0 < B):
                count -= 1
                B -= 1
            else:
                score -=1
                count -=1

    print(score)



### FIXED CODE ###

A,B,C,K = map(int,input().split())

count = K
score = 0

if(K <= A):
    print(K)
elif(K <= (A+B)):
    print(A)
else:
    print(A-(K-(A+B)))
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    import bisect 
    n = int(input())
    l = list(map(int,input().split()))
    l1 = [0]*n
    for i in range(n):
        l1[l[i]-1] = i
    ans = 0
    s = [-1,-1,l1[-1],n,n]

    for i in range(n-2,-1,-1):
        c = l1[i]
        now = bisect.bisect_right(s,c)
        a = s[now-2]
        b = s[now-1]
        d = s[now]
        e = s[now+1]
        count = (b-a)*(d-c) + (e-d)*(c-b)
        s.insert(now,c)
        ans += count*(i+1)
    print(ans)
if __name__ == "__main__":
    main()

### FIXED CODE ###

n=int(input())
p=list(map(int,input().split()))
id=[0]*(n+1)
for i,p_i in enumerate(p):
    id[p_i]=i

r = list(range(1,n+1))+[n,n]
l = list(range(-1,n-1))+[-1,-1]
ans=0
for p in range(1,n+1):
    x=id[p]
    r1=r[x]
    r2=r[r1]
    l1=l[x]
    l2=l[l1]
    ans+=p*((x-l1)*(r2-r1) + (l1-l2)*(r1-x))
    r[l1]=r1
    l[r1]=l1
print(ans)
### BUGGY CODE ###

def main():
    import queue
    n,m = map(int,input().split())
    A = []
    for _ in range(m):
        a = int(input())
        A.append(a)
    mod = 10**9+7
    q = queue.Queue()
    q.put(1)
    if 1 in A:
        q.put(0)
    else:
        q.put(1)
    for i in range(2,n+1):
        if i in A:
            q.get()
            q.put(0)
        else:
            a = q.get()
            b = q.get()
            q.put(b)
            q.put((a+b)%mod)

    q.get()
    print(q.get())

if __name__ == "__main__":
    main()

### FIXED CODE ###

from functools import lru_cache

def main():
    n,m = map(int,input().split())
    import numpy as np
    ans = np.ones(n+1,dtype=int)*-1
    ans[0] = 1
    mod = 10**9+7
    for _ in range(m):
        a = int(input())
        ans[a]=0
    if ans[1]!=0:
        ans[1]=1
    for i in range(2,n+1):
        if ans[i]!=0:
            ans[i] = (ans[i-1]+ans[i-2])%mod
    print(ans[-1])
        

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

def func(x,y,z):
    ans = x**2 + y**2 + z**2+ x*y + y*z + z*x
    #print("x={},y={},z={},ans={}".format(x,y,z,ans))
    return ans

N = int(input())
for n in range(1,N+1):
    count = 0
    for x in range(1,N+1):
        for y in range(1,N+1):
            for z in range(1,N+1):
                if func(x,y,z)==n:
                    count=count+1
    print(count)
                

### FIXED CODE ###


import math
def func(x,y,z):
    ans = x**2 + y**2 + z**2+ x*y + y*z + z*x
    return ans

N = int(input())
array_N = [0]*N
root_n = round(math.sqrt(N+1))

for x in range(1,root_n):
    for y in range(1,root_n):
        for z in range(1,root_n):
            if func(x,y,z) <= N:
                array_N[func(x,y,z)-1] = array_N[func(x,y,z)-1] +1
                
for i in range(N):
    print(array_N[i])
### BUGGY CODE ###

a, b, c, k = map(int, input().split())

ans = 0
for i in range(k):
    if i+1 <= a:
        ans = ans + 1

    if i+1 > a + b:
        ans = ans -1

print(ans)


### FIXED CODE ###

a, b, c, k = map(int, input().split())

ans = a
if k < a:
    ans = k
    
if k > a + b:
    ans = ans - (k - (a+b))

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

A,B,C,D=map(int,input().split())
cnt=0
for i in range(A,B+1):
    if i%C==0 or i%D==0:
        cnt+=1
    else:
        continue
print(B-A+1-cnt)

### FIXED CODE ###

import fractions
A,B,C,D=map(int,input().split())
L=C*D//(fractions.gcd(C,D))
print(int(B-A+1-(B//C-((A-1)//C))-(B//D-((A-1)//D))+(B//L-((A-1)//L))))
### BUGGY CODE ###

import math

N = int(input())

ans = 0

for a in range(1, N+1):
  for b in range(1, N+1):
    for c in range(1, N+1):
      ans = ans + math.gcd(math.gcd(a, b), c)

print(ans)

### FIXED CODE ###

import math
import itertools

N = int(input())

ans1 = sum(range(1, N+1))

ans2 = 0
for x in itertools.combinations(range(1, N+1), 3):
  ans2 = ans2 + math.gcd(math.gcd(x[0],x[1]),x[2]);


ans2 = ans2 * 6

ans3 = 0
for x in itertools.combinations(range(1, N+1), 2):
  ans3 = ans3 + math.gcd(math.gcd(x[0],x[0]),x[1]);


ans3 = ans3 * 6

print(ans1 + ans2 + ans3)