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

# 解説みたよ
import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline
n, m = map(int, input().split())
es = [[] for i in range(n)]
l, r, d = [0] * m, [0] * m, [0] * m
for i in range(m):
    l[i], r[i], d[i] = map(int, input().split())
    l[i] -= 1
    r[i] -= 1
    es[l[i]].append((r[i], d[i]))
    es[r[i]].append((l[i], -d[i]))
INF = 1000000000000
value = [INF] * n


def dfs(v):
    for i, di in es[v]:
        if value[i] == INF:
            value[i] = value[v] + di
            dfs(i)


for i in range(n):
    if value[i] == INF:
        value[i] = 0
        dfs(i)

for i in range(m):
    if value[r[i]] - value[l[i]] != d[i]:
        print("No")
        exit()
print("Yes")


### FIXED CODE ###

# 解説みたよ
import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline
n, m = map(int, input().split())
es = [[] for i in range(n)]
l, r, d = [0] * m, [0] * m, [0] * m
for i in range(m):
    l[i], r[i], d[i] = map(int, input().split())
    l[i] -= 1
    r[i] -= 1
    es[l[i]].append((r[i], d[i]))
    es[r[i]].append((l[i], -d[i]))
INF = 1000000000000
value = [INF] * n


def dfs(v):
    for i, di in es[v]:
        if value[i] == INF:
            value[i] = value[v] + di
            dfs(i)


for i in range(n):
    if value[i] == INF:
        value[i] = 0
        dfs(i)

for i, j, k in zip(l, r, d):
    if value[j] - value[i] != k:
        print("No")
        exit()
print("Yes")
### BUGGY CODE ###

n = int(input())
A = [int(i) for i in input().split()]
while True:
    if len(A) == 1:
        print(A[0])
        break
    A[A.index(max(A))] %= min(A)
    if 0 in A:
        A.remove(0)

### FIXED CODE ###

n = int(input())
A = [int(i) for i in input().split()]

def gcd(x, y):
    while y > 0:
        x, y = y, x % y
    return x

for i in range(n - 1):
    A[i + 1] = gcd(A[i], A[i + 1])
    
print(A[-1])
### BUGGY CODE ###

import numpy as np
import random

mod=998244353


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

#n,m=10,10
#A=[[int(random.randint(0,1)) for j in range(m)] for i in range(n)]


#A=np.array(A)

#print(A)
i=0
j=0
while i<n and j<m :
    #for ii in range(len(A)):
        #print(A[ii])
    #print("\n")
    t=0
    #print(A[i][j])
    if A[i][j]==0 :
        #print("B")
        k=i
        while k<n and A[k][j]==0 :
            k+=1
        #print(str(i)+" "+str(k))
        if k<n :
            #print(A)
            #B=[A[i][0],A[i][1]]
            #A[i]=[A[k][0],A[k][1]]
            #A[k]=[B[0],B[1]]
            for u in range(m):
                A[i][u],A[k][u]=A[k][u],A[i][u]

            #print(A)
        else :
            t=1
            j+=1
    #print(t)
    if t==0 :
        #print("A")
        #print(i)
        for p in range(i+1,n):
            #print("AA")
            if A[p][j]>0 :
                #print(p)
                for kk in range(m):
                    A[p][kk]=(A[p][kk]-A[i][kk])%2
        i+=1
        j+=1


#for i in range(len(A)):
#    print(A[i])

r=0
j=0
for i in range(m):
    if j<n :
        if A[j][i]!=0 :
            r+=1
            j+=1

for i in range(n):
    for j in range(m):
        A[i][j]=int(A[i][j])
#print(A)
#print(r) #rank

a=1
b=1

for i in range(n+m-1):
    a=(a*2)%mod
for i in range(n+m-1-r):
    b=(b*2)%mod

print((a-b)%mod)


### FIXED CODE ###

import numpy as np
import random

mod=998244353


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

#n,m=300,300
#A=[[int(random.randint(0,1)) for j in range(m)] for i in range(n)]


#A=np.array(A)

#print("A")
i=0
j=0
r=0 #rank
while i<n and j<m :
    #print(i)
    t=0
    if A[i][j]==0 :
        k=i
        while k<n and A[k][j]==0 :
            k+=1
        if k<n :
            A[i],A[k]=A[k],A[i]

            #print(A)
        else :
            t=1
            j+=1
    if t==0 :
        r+=1
        for p in range(i+1,n):
            if A[p][j]>0 :
                for kk in range(j,m):
                    A[p][kk]=(A[p][kk]-A[i][kk])%2
        i+=1
        j+=1



#r=0
#j=0
#for i in range(m):
#    if j<n :
#        if A[j][i]!=0 :
#            r+=1
#            j+=1

for i in range(n):
    for j in range(m):
        A[i][j]=int(A[i][j])
#print(A)
#print(r) #rank

a=1
b=1

for i in range(n+m-1):
    a=(a*2)%mod
for i in range(n+m-1-r):
    b=(b*2)%mod

print((a-b)%mod)
### BUGGY CODE ###

s = list(input())
answer = 0

for i in range(4, len(s)):
    for j in range(0, len(s) - i):
        num = int(''.join(s[j:(i + j + 1)]))
        if num % 2019 == 0:
            answer += 1

print(answer)


### FIXED CODE ###

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
### BUGGY CODE ###

import numpy as np
N,W=map(int,input().split())
w=[]
v=[]
maxV=0
for i in range(N):
    a,b=map(int,input().split())
    if maxV<b:
        maxV=b
    w.append(a)
    v.append(b)
w=np.array(w)
v=np.array(v)
#dp[n個目のアイテムまでで][V以上を達成する]=最小のw
#dp[0][v]=inf ゼロ個でｖは無理なので
#dp[0][0]=0と初期化する
#だからiの時dp[i][v]=min(dp[i-1][v],dp[i-1][V-v[i-1]]+w[i])である<-i-1なのはvとかにはゼロ個とかないので
#V-v[i]<0ならば、とれないので前者になるね！！
#これをi=0(は初期化でする)->nまでおこない、各iについてはとりうる最大のValueを考えるが
#これは最大で各アイテムについて最大のVがあってこれにアイテム数Nを掛けたものである
#つまりdpのサイズはdp[0->N][0->maxV*N]をとればよい

dp=[[float("inf") for i in range(maxV*(N+1))] for j in range(N+1)]
dp[0][0]=0

for i in range(1,N+1):
    for val in range(maxV*N+1):
        tmp1=dp[i-1][val]#とらない
        if val-v[i-1]<0:#この時、iこめの価値がおおきいので、これをとるだけで達成してしまう
            tmp2=w[i-1]#i=1の時、dp[0][val]=inf
        else:#i=1の時val-v[0]>0で無限になるので
            tmp2=dp[i-1][val-v[i-1]]+w[i-1]#
        res=min(tmp1,tmp2)
        dp[i][val]=res
#ここでW以下となるvalの最大値をたんさくする
max=0
for value in range(len(dp[N])):
    if dp[N][value]<=W:
        if value>max:
            max=value
print(max)

### FIXED CODE ###

N,W=map(int,input().split())
w=[]
v=[]
maxV=0
for i in range(N):
    a,b=map(int,input().split())
    if maxV<b:
        maxV=b
    w.append(a)
    v.append(b)
#dp[n個目のアイテムまでで][V以上を達成する]=最小のw
#dp[0][v]=inf ゼロ個でｖは無理なので
#dp[0][0]=0と初期化する
#だからiの時dp[i][v]=min(dp[i-1][v],dp[i-1][V-v[i-1]]+w[i])である<-i-1なのはvとかにはゼロ個とかないので
#V-v[i]<0ならば、とれないので前者になるね！！
#これをi=0(は初期化でする)->nまでおこない、各iについてはとりうる最大のValueを考えるが
#これは最大で各アイテムについて最大のVがあってこれにアイテム数Nを掛けたものである
#つまりdpのサイズはdp[0->N][0->maxV*N]をとればよい

dp=[[float("inf") for i in range(maxV*(N+1))] for j in range(N+1)]
dp[0][0]=0

for i in range(1,N+1):
    for val in range(maxV*N+1):
        tmp1=dp[i-1][val]#とらない
        if val-v[i-1]<0:#この時、iこめの価値がおおきいので、これをとるだけで達成してしまう
            tmp2=w[i-1]#i=1の時、dp[0][val]=inf
        else:#i=1の時val-v[0]>0で無限になるので
            tmp2=dp[i-1][val-v[i-1]]+w[i-1]#
        res=min(tmp1,tmp2)
        dp[i][val]=res
#ここでW以下となるvalの最大値をたんさくする
max=0
for value in range(len(dp[N])):
    if dp[N][value]<=W:
        if value>max:
            max=value
print(max)
### BUGGY CODE ###

from collections import deque
def start_search(G):
    start=[]
    for i in range(H):
        for j in range(W):
            if G[i][j]=='#':
                start.append((i,j))
    return start
def bfs(G,visited,start):
    queue=deque(start)
    cnt=0
    for p,q in start:
        visited[p][q]=0
    while queue:
        tmp=len(queue)
        for _ in range(tmp):
            (y,x)=queue.popleft()
            for j,k in ([1,0],[0,1],[-1,0],[0,-1]):
                tmp_y,tmp_x = y+j,x+k
                if 0<=tmp_y<=H-1 and 0<=tmp_x<=W-1 and visited[tmp_y][tmp_x]==-1:
                    visited[tmp_y][tmp_x]=visited[y][x]+1
                    queue.append([tmp_y,tmp_x])
        cnt+=1
    return cnt-1
if __name__=="__main__":
    H,W = map(int,input().split())
    G=[input() for _ in range(H)]
    start=start_search(G)
    visited=[[-1]*W for _ in range(H)]
    print(bfs(G,visited,start))


### FIXED CODE ###

from collections import deque
def start_search(G):
    start=[]
    for i in range(H):
        for j in range(W):
            if G[i][j]=='#':
                start.append((i,j))
    return start
def bfs(G,visited,start):
    queue=deque(start)
    cnt=0
    for p,q in start:
        visited[p][q]=0
    while queue:
        tmp=len(queue)
        for _ in range(tmp):
            (y,x)=queue.popleft()
            for j,k in ([1,0],[0,1],[-1,0],[0,-1]):
                tmp_y,tmp_x = y+j,x+k
                if 0<=tmp_y<=H-1 and 0<=tmp_x<=W-1 and visited[tmp_y][tmp_x]==-1:
                    visited[tmp_y][tmp_x]=visited[y][x]+1
                    queue.append([tmp_y,tmp_x])
        cnt+=1
    return cnt-1
if __name__=="__main__":
    H,W = map(int,input().split())
    G=[input() for _ in range(H)]
    start=start_search(G)
    visited=[[-1]*W for _ in range(H)]
    print(bfs(G,visited,start))
### BUGGY CODE ###

from queue import Queue

N,X,Y=map(int,input().split())

inf=1001001001
answer=[0]*(N-1)

for j in range(N):
    v=[inf]*N
    q=Queue()
    q.put(j)
    #print(q)
    v[j]=0
    while not q.empty():
        i=q.get()
        if i-1>=0 and v[i-1]==inf:
            v[i-1]=v[i]+1
            q.put(i-1)
            #print(i-1)
        if i+1<N and v[i+1]==inf:
            v[i+1]=v[i]+1
            q.put(i+1)
            #print(i+1)
        if i==X-1 and v[Y-1]==inf:
            v[Y-1]=v[i]+1
            q.put(Y-1)

        if i==Y-1 and v[X-1]==inf:
            v[X-1]=v[i]+1
            q.put(X-1)
        #print(v)
    #print(v)
    for k in v:
        if k>0:
            answer[k-1]+=1
for a in answer:
    print(a//2)




### FIXED CODE ###

N,X,Y=map(int,input().split())

X-=1
Y-=1

dist=[0]*(N+1)


for i in range(N):
    for j in range(i+1,N):
        dist[(min(abs(i-j),abs(i-Y)+abs(X-j)+1,abs(i-X)+abs(Y-j)+1))]+=1
for d in range(1,N):
    print(dist[d])
### BUGGY CODE ###

N,M=map(int,input().split())
ListAbeta=list(map(int,input().split()))
ListA=sorted(ListAbeta)
ListBC=[]
m=1
while m<=M:
    ListBC.append(list(map(int,input().split())))
    b=1
    while b<=ListBC[m-1][0]:
        if ListA[b-1]>=ListBC[m-1][1]:
            break
        else:
            ListA[b-1]=ListBC[m-1][1]
            b+=1
    ListA=sorted(ListA)
    m+=1
    b=0
print(sum(ListA))

### FIXED CODE ###

N,M=map(int,input().split())
LA=list(map(int,input().split()))
L=[]
for i in LA:
    L.extend([[1,i]])
for m in range(M):
    B,C=map(int,input().split())
    L.extend([[B,C]])
L.sort(key=lambda _:_[1] ,reverse=True)

ans=0
n=0
x=0
while x<=N-1:
    y=0
    while y<=L[n][0]-1:
        ans+=L[n][1]
        y+=1
        x+=1
        if x==N:
            break
        else:
            pass
    n+=1

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

import bisect
A, B, Q = map(int, input().split())
INF = 10 ** 18
s = [-INF] + [int(input()) for i in range(A)] + [INF]
t = [-INF] + [int(input()) for i in range(B)] + [INF]
for q in range(Q):
  x = int(input())
  b, d = bisect.bisect_left(s, x), bisect.bisect_left(t, x)
  res = INF
  for S in [s[b - 1], s[b]]:
    for T in [t[d - 1], t[d]]:
      d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
      res = min(res, d1, d2)
  print(res)

### FIXED CODE ###

import bisect
A, B, Q = map(int, input().split())
INF = 10 ** 18
s = [-INF] + [int(input()) for i in range(A)] + [INF]
t = [-INF] + [int(input()) for i in range(B)] + [INF]
for q in range(Q):
  x = int(input())
  b, d = bisect.bisect_right(s, x), bisect.bisect_right(t, x)
  res = INF
  for S in [s[b - 1], s[b]]:
    for T in [t[d - 1], t[d]]:
      d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
      res = min(res, d1, d2)
  print(res)
### BUGGY CODE ###

N=int(input())
a=[]
for i in range(N):
  a.append(input())
b=list(set(a))
b.sort()
c=list(map(lambda x:a.count(x),b))
d=int(c.count(max(c)))
e=[]
for k in range(d):
  e.append(b[c.index(max(c))])
  c[c.index(max(c))]=0
for l in e:
  print(l)

### FIXED CODE ###

N=int(input())
a=[]
for i in range(N):
  a.append(input())
b={}
for j in range(len(a)):
  if a[j] in b:
    b[a[j]]+=1
  else:
    b[a[j]]=1
max_b=max(b.values())
c=[]
for k,l in b.items():
  if l==max_b:
    c.append(k)
c.sort()
for m in c:
  print(m)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
prod = 1
def main():
    if 0 in A:
        print(0)
        return
    prod = 1
    for a in A:
        prod *= a
    if prod > 1000000000000000000:
        print(-1)
        return
    print(prod)
main()

### FIXED CODE ###

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

#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix

from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！

def main():
    n,m,*a=map(int,open(0).read().split())
    dp=defaultdict(int)
    dp[0]=1
    mod=10**9+7
    for i in range(1,n+1):
        if i in a:
            continue
        dp[i]=dp[i-1]%mod
        if i>1:
            dp[i]+=dp[i-2]%mod
    print(dp[n]%mod)
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix

from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！

def main():
    n,m,*a=map(int,open(0).read().split())
    dp=[0]*(n+1)
    a=set(a)
    dp[0]=1
    mod=10**9+7
#    dp[1]=dp[0]%mod
    for i in range(1,n+1):
        if i in a:
            continue
        else:
            dp[i]=(dp[i-1]+dp[i-2])%mod
    print(dp[n]%mod)
#    print(dp)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

mod = 10**9 + 7
s = input()
n = len(s)
dp = [[0]*13 for i in range(n+1)]
dp[0][0] = 1
for i, si in enumerate(s):
  if si == '?':
    for ss in range(10):
      for j in range(13):
        dp[i+1][(j*10+ss)%13] += dp[i][j]
        dp[i+1][(j*10+ss)%13] %= mod
  else:
    ss = int(si)
    for j in range(13):
      dp[i+1][(j*10+ss)%13] += dp[i][j]
      dp[i+1][(j*10+ss)%13] %= mod
#print(dp)
print(dp[n][5])

### FIXED CODE ###

mod = 10**9 + 7
s = input()
n = len(s)
dp = [[0]*13 for i in range(n+1)]
dp[0][0] = 1
for i, si in enumerate(s):
  if si == '?':
    for ss in range(10):
      for j in range(13):
        dp[i+1][(j*10+ss)%13] += dp[i][j]
        dp[i+1][(j*10+ss)%13] %= mod
  else:
    ss = int(si)
    for j in range(13):
      dp[i+1][(j*10+ss)%13] += dp[i][j]
      dp[i+1][(j*10+ss)%13] %= mod
#print(dp)
print(dp[n][5])
### BUGGY CODE ###

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


### FIXED CODE ###

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

n = int(input())
S = [int(x) for x in input().split()]
q = int(input())
T = [int(x) for x in input().split()]


res = 0

for num in T:
    if num in S:
        res += 1

print(res)

### FIXED CODE ###

len_a = input()
a = set(map(int, input().split()))
len_b = input()
b = set(map(int, input().split()))

print(len(a & b))
### BUGGY CODE ###

input()
a = map(int, input().split())
b = 1
for i in a:
    b*=i

if b>1e18:
    b=-1;
print(b)


### FIXED CODE ###

input()
a = list(map(int, input().split()))
a.sort()
b = 1
for i in a:
    b*=i
    if b>1e18:
        print(-1)
        exit()

# if b>1e18:
#     b=-1;
print(b)
### BUGGY CODE ###

MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))
s = 0
for i in range(N-1):
    for j in range(i+1, N):
      s = (s + (A[i]^A[j])) % MOD
print(s)

### FIXED CODE ###

MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))
s = 0
n = len(bin(max(A))[2:])
for i in range(n):
  b = 1<<i
  N_t = sum([1 for Ai in A if (b&Ai)>0])
  N_f = N-N_t
  s += (1<<i) * N_t * N_f
print(s%MOD)
### BUGGY CODE ###

import math

def make_prime_list_2(num):
    if num < 2:
        return []

    # 0のものは素数じゃないとする
    prime_list = [i for i in range(num + 1)]
    prime_list[1] = 0 # 1は素数ではない
    num_sqrt = math.sqrt(num)

    for prime in prime_list:
        if prime == 0:
            continue
        if prime > num_sqrt:
            break

        for non_prime in range(2 * prime, num, prime):
            prime_list[non_prime] = 0

    return [prime for prime in prime_list if prime != 0]

def search_divisor_num_1(num):
    if num < 0:
        return None
    elif num == 1:
        return 1
    else:
        num_sqrt = math.floor(math.sqrt(num))
        prime_list = make_prime_list_2(num_sqrt)

        divisor_num = 1
        for prime in prime_list:
            count = 1
            while num % prime == 0:
                num //= prime
                count += 1
            divisor_num *= count

        if num != 1:
            divisor_num *= 2

        return divisor_num

n=int(input())
print(sum(search_divisor_num_1(i) for i in range(1,n)))


### FIXED CODE ###

def num_divisors_table(n):
    table = [0] * (n + 1)
    
    for i in range(1, n + 1):
        for j in range(i, n + 1, i):
            table[j] += 1
    
    return table
n=int(input())
print(sum(num_divisors_table(n-1)))
### BUGGY CODE ###

n = int(input())
s = [input() for _ in range(n)]

d = {}
for i in range(n):
  if s[i] in d.keys():
    d[s[i]] += 1
  else:
    d[s[i]] = 1

m = max(d.values())

ans = [k for k, v in d.items() if v == m]
ans.sort()

print(*ans, sep = "\n")

### FIXED CODE ###

from collections import Counter

n = int(input())
s = [input() for _ in range(n)]

c = Counter(s)
c = c.most_common()
ans_number = c[0][1]
c.sort()

for i in range(len(c)):
  if c[i][1] == ans_number:
    print(c[i][0])
### BUGGY CODE ###

n,k = [int(x) for x in input().strip().split()]
H = [int(x) for x in input().strip().split()]

inf = int(10e9 + 7)
dp = [inf] * n
dp[0] = 0
for i in range(n):
    for j in range(i+1,min(n,i+k+1)):
        dp[j] = min (dp[j], dp[i] + abs(H[i] - H[j]))
print (dp[-1])

### FIXED CODE ###

n,k = [int(x) for x in input().strip().split()]
H = [int(x) for x in input().strip().split()]

inf = int(10e9 + 7)
dp = [inf] * n
dp[0] = 0
for i in range(n):
    for j in range(i+1,min(n,i+k+1)):
        dp[j] = min (dp[j], dp[i] + abs(H[i] - H[j]))
print (dp[-1])
### BUGGY CODE ###

import math
from functools import reduce


k = int(input())

def gcd(*numbers):
    return reduce(math.gcd, numbers)

k += 1
ans = 0


for i in range(1,k):
    for j in range(1,k):
        for h in range(1,k):
            #print(i,j,h)
            ans += gcd(i,j,h)


print(ans)


### FIXED CODE ###

import math
from functools import reduce


k = int(input())

def gcd(*numbers):
    return reduce(math.gcd, numbers)

k += 1
ans = 0

for i in range(1,k):
    for j in range(i,k):
        #print(i,j)
        if i == j:
            ans += gcd(i,j)
        else:
            ans += gcd(i,j)*6

for i in range(1,k):
    for j in range((i+1),k):
        for h in range((j+1),k):
            #print(i,j,h)
            ans += gcd(i,j,h)*6


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

import sys
from copy import copy
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

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

graph = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    graph[u].append(v)
    graph[v].append(u)

ans = [0] * n


def dfs(v, v_p, dp):
    # print(v, v_p, dp)
    ans[v] = len(dp)
    for v_next in graph[v]:
        if v_next == v_p:
            continue

        # print(dp)
        dp2 = copy(dp)
        if a[v_next] > dp2[-1]:
            dp2.append(a[v_next])
            dfs(v_next, v, dp2)
            dp2 = dp2[:len(dp2) - 1]
        else:
            idx = bisect_left(dp2, a[v_next])
            past = dp2[idx]
            dp2[idx] = a[v_next]
            dfs(v_next, v, dp2)
            dp2[idx] = past


dfs(0, -1, [a[0]])
print(*ans, sep='\n')


### FIXED CODE ###

import sys
from copy import copy
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

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

graph = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    graph[u].append(v)
    graph[v].append(u)

ans = [0] * n
dp = [float('inf')] * n
dp[0] = a[0]


def dfs(v, v_p, dp_len):
    # print(v, v_p, dp)
    ans[v] = dp_len
    for v_next in graph[v]:
        if v_next == v_p:
            continue

        # print(dp)
        if a[v_next] > dp[dp_len - 1]:
            past = dp[dp_len]
            dp[dp_len] = a[v_next]
            dfs(v_next, v, dp_len + 1)
            dp[dp_len] = past
        else:
            idx = bisect_left(dp, a[v_next])
            # always idx < dp_len
            past = dp[idx]
            dp[idx] = a[v_next]
            dfs(v_next, v, dp_len)
            dp[idx] = past


dfs(0, -1, 1)
print(*ans, sep='\n')
### BUGGY CODE ###

import numpy as np
N = int(input())
a = [int(input()) for i in range(N)]

a = np.array(a)
max_a = np.max(a)
max_idx = np.where(a == max_a)[0]

if len(max_idx) != 1:
    for i in range(N):
        print(max_a)
else:
    premax_a = np.max(np.hstack((a[0:max_idx[0]], a[max_idx[0]+1:])))
    for i in range(N):
        if i == max_idx:
            print(premax_a)
        else:
            print(max_a)

### FIXED CODE ###

import numpy as np
N = int(input())
a = [int(input()) for i in range(N)]

# a = np.array(a)
max_a = np.max(a)
premax_a = np.sort(a)[::-1][1]

for i in range(N):
    if a[i] == max_a:
        print(premax_a)
    else:
        print(max_a)
### BUGGY CODE ###

import math
S =  list(map(int,input().split()))
A = S[0]
B = S[1]
N = S[2]
d = []
for i in range(1,N+1):
    t = math.floor(A*i/B)-math.floor(i/B)*A
    d.append(t)
print(max(d))


### FIXED CODE ###

import math
S =  list(map(int,input().split()))
A = S[0]
B = S[1]
N = S[2]
if N<B:
    print(math.floor(A*N/B)-math.floor(N/B)*A)
else:
    print(math.floor(A*(B-1)/B)-math.floor((B-1)/B)*A)
### BUGGY CODE ###

N=int(input())
S={"R":[],"G":[],"B":[]}
for i,s in enumerate(input()):
	S[s].append(i)

lis = [sorted([a, b, c]) for a in S["R"] for b in S["G"] for c in S["B"]]
print(len([1 for i,j,k in lis if j-i!=k-j]))

### FIXED CODE ###

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

ans = S.count("R")*S.count("G")*S.count("B")

for i in range(N):
	for j in range(N-i):
		if i+2*j>=N:
			break
		elif S[i]!=S[i+j] and S[i]!=S[i+2*j] and S[i+j]!=S[i+2*j]:
			ans-=1
print(ans)