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

#coding:utf-8

def main():
    h, n = map(int, input().split())
    ab = []
    for _ in range(n):
        ab.append(list(map(int, input().split())))
    
    inf = 100000000000
    # indexがモンスターに与えたダメージで、中身がトキのダメージ
    damages = [inf for _ in range(100000)]
    damages[0] = 0
    for i in range(1, h + 1):
        for j in range(n):
            damage_monster = ab[j][0]
            damage_toki = ab[j][1]
            
            damages[i] = min(damages[max(0, i - damage_monster)] + damage_toki, damages[i])


    print(min(damages[h:]))
main()

### FIXED CODE ###

#coding:utf-8

def main():
    h, n = map(int, input().split())
    ab = []
    for _ in range(n):
        ab.append(list(map(int, input().split())))
    
    inf = 100000000000
    # indexがモンスターに与えたダメージで、中身がトキのダメージ
    damages = [0] + [inf] * h
    for i in range(1, h + 1):
        for j in range(n):
            damage_monster = ab[j][0]
            damage_toki = ab[j][1]
            
            damages[i] = min(damages[max(0, i - damage_monster)] + damage_toki, damages[i])


    print(min(damages[h:]))
main()
### BUGGY CODE ###

S=input()
count=0

while 1:
    tmp=S.count('BW')
    if tmp==0:
        break

    count=count+tmp
    S=S.replace('BW','WB')

print(count)

### FIXED CODE ###

S=input()

tmp=[i for i, x in enumerate(S) if x == 'W']
print(sum(tmp)-sum(range(len(tmp))))
### BUGGY CODE ###

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

q = 1

for i in num:
    q=q*i

if q>1e18: print(-1)
else: print(q)
        


### FIXED CODE ###

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

cont=0
ans=1

for j in num:
    if j == 0: cont+=1

if cont > 0: print(0)
else:
    for i in num:
        ans=ans*i
        if ans>1e18:
            ans=-1
            break
    print(ans)
### BUGGY CODE ###

import itertools

n = int(input())
s = input()
nums = set()

conb = list(itertools.combinations(s, 3))
#print(conb)

for i in range(len(conb)):
    nums.add(str(conb[i]))

#print(nums)
print(len(nums))

### FIXED CODE ###

n = int(input())
s = input()
ans = 0

def isAvailable(pw):
    for i in range(len(s)):
        if s[i] == pw[0]:
            pw = pw[1:]
            if pw == '':
                break

    if len(pw) == 0:
        return True
    else:
        return False

for i in range(10):
    for j in range(10):
        for k in range(10):
            pw = str(i) + str(j) + str(k)
            if isAvailable(pw):
                ans += 1

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

n = int(input())
s = input()
cou = 0
for i in range(1000):
  i = "{0:03d}".format(i)
  t = 0
  r = 0
  while r!=n:
    if s[r]==i[t]:
      t += 1
    if t==3:
      t = 0
      cou += 1
      r = n-1
    r += 1
    
              
print(cou)

### FIXED CODE ###

n = int(input())
s = input()
cou = 0
for i in range(1000):
  i = "{0:03d}".format(i)
  t = 0
  r = 0
  while r!=n:
    if s[r]==i[t]:
      t += 1
    if t==3:
      cou += 1
      r = n-1
    r += 1            
print(cou)
### BUGGY CODE ###

import array
import heapq
def SME(start,end):
    A = []
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx]==0 : continue
                else :
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if ANS[i]==0 : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i]==0 : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS
 
[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
parameter = 0.995
ANS = array.array('I',[0]*N)
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

r1, c1, r2, c2 = map(int, input().split())
mod = 10**9+7

import numpy as np
graph = [[1]*(r2+1) for _ in range(c2+1)]
graph = np.array(graph)

for i in range(1, c2+1):
    graph[i][1:] = (graph[0][:-1] + np.cumsum(graph[i-1][1:]))%mod

cum_graph = (np.cumsum(np.cumsum(graph, axis=0), axis=1))%mod

print((cum_graph[c2][r2]-cum_graph[c1-1][r2]-cum_graph[c2][r1-1]+cum_graph[c1-1][r1-1])%mod)
    


### FIXED CODE ###

MOD = 10**9+7
r1,c1,r2,c2 = map(int,input().split())
 
size = 1010000*2
f_list = [1]*(size)
for i in range(1,size):
    f_list[i] = (f_list[i-1]*i)%MOD

def func(r,c):
    return (f_list[r+c]*pow(f_list[r],MOD-2,MOD)*pow(f_list[c],MOD-2,MOD))
 
ans = func(r2+1,c2+1)-1
ans += func(r1,c1)-1
ans -= func(r2+1,c1)-1
ans -= func(r1,c2+1)-1
print(ans%MOD)
### BUGGY CODE ###

N,M=map(int,input().split())
*A,=map(int,input().split())
d={}
for a in A:
    k=a
    while k>=1:
        d[k-k//2]=d.get(k-k//2,0)+1
        k=k//2
s=0
i=0
for k in sorted(list(d.keys()), key=lambda x:-x):
    if i+d[k]<=M:
        i+=d[k]
        s+=k*d[k]
    else:
        s+=k*(M-i)
        break
print(sum(A)-s)

### FIXED CODE ###

def f():
  N,M=map(int,input().split())
  *A,=map(int,input().split())
  l=[]
  for a in A:
      k=a
      while k>=1:
          l+=[k-k//2]
          k=k//2
  print(sum(A)-sum(sorted(l)[-M:]))
if __name__=="__main__":
  f()
### BUGGY CODE ###

#!/usr/bin/env python3
n, k, *p = map(int, open(0).read().split())
ans = float()
for i in range(n - k + 1):
    ans = max(ans, (sum(p[i:k + i]) + k) / 2)
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
n, k, *P = map(int, open(0).read().split())
p = [(i + 1) / 2 for i in P]
c = sum(p[:k])
ans = c
for i in range(n - k):
    c = c + p[i + k] - p[i]
    ans = max(c, ans)
print(ans)
### BUGGY CODE ###

N = int(input())

if N%2==1:
    print(0)
    exit()
elif N==0 or N==2:
    print(0)
    exit()

M = (N//2)//2
two = (N//2) + M*(M+1)//2

go = 0

go_dict = {}
for i in range(10, N+1, 10):
    index = i
    cnt = 0
    while index % 5==0:
        if (index//5) in go_dict:
            cnt += go_dict[index//5]+1
            break
        else:
            index /= 5
            cnt+=1
    go_dict[i] = cnt
    go += cnt


print(min(two, go))


### FIXED CODE ###

#!/usr/bin/env python3

N = int(input())

if N % 2 == 1:
    print(0)
else:
    ret = 0
    for i in range(1, 27):
        ret += N // (2*5**i)


    print(ret)
### BUGGY CODE ###

import numpy as np
N = int(input())
A = np.array(list(map(int,input().split(" "))))
Q = int(input())
B = [list(map(int,input().split(" "))) for i in range(0,Q)]

for i in range(0,Q):
    before = B[i][0]
    after  = B[i][1]
    X = (A == before)
    A[X] = after
    print(np.sum(A))
#print("\n".join(list(map(str,A.tolist()))))

### FIXED CODE ###

import collections
N = int(input())
A = list(map(int,input().split(" ")))
Q = int(input())
B = [list(map(int,input().split(" "))) for i in range(0,Q)]
ans = sum(A)
num = collections.Counter(A)
for i in range(0,Q):
    before, after = B[i][0], B[i][1]
    ans += num[before] * (after - before)
    num[after] += num[before]
    num[before] = 0
    print(ans)
### BUGGY CODE ###

from collections import deque

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

rev_p = [0] * (n * n)
for offset in range(len(p)):
    rev_p[p[offset] - 1] = offset

costs = [0] * (n * n)

for i in range(n*n):
    costs[i] = min(i // n, n - i // n - 1, i % n, n - i % n - 1)

removed = set()

ans = 0
for i, pi in enumerate(p):
    ans += costs[pi-1]
    removed.add(pi-1)

    d = deque()
    d.append((pi-1, costs[pi-1]))

    while d:
        pos, cost = d.popleft()

        for offset in [-1, -n, 1, n]:
            if 0 <= pos + offset < n * n:
                next_cost = cost if pos in removed else cost + 1

                if costs[pos+offset] > next_cost:
                    costs[pos+offset] = next_cost
                    d.append((pos+offset, next_cost))

print(ans)


### FIXED CODE ###

from collections import deque

n = int(input())
n2 = n * n
p = list(map(int, input().split()))

costs = [0] * n2

for i in range(n2):
    costs[i] = min(i // n, n - i // n - 1, i % n, n - i % n - 1)

remains = [1] * n2

ans = 0
for i, pi in enumerate(p):
    ans += costs[pi-1]
    remains[pi-1] = 0

    d = deque()
    d.append((pi-1, costs[pi-1]))

    while d:
        pos, cost = d.popleft()

        for offset in [-1, -n, 1, n]:
            if 0 <= pos + offset < n2:
                next_cost = cost + remains[pos]

                if costs[pos+offset] > next_cost:
                    costs[pos+offset] = next_cost
                    d.append((pos+offset, next_cost))

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

n, m = map(int,input().split())
    
tbin_o = []
for i in range(m):
    xxx = list(map(int,input().split()))
    if xxx[0] == 1 or xxx[1] == n:
        tbin_o.append(xxx)



aaa = 0
for j in range(len(tbin_o)):
    for l in range(len(tbin_o)):
        if tbin_o[j][1] == tbin_o[l][0] and j != l:
            aaa = aaa + 1
            break
            
if aaa == 1 :
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

### FIXED CODE ###

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

boolins =[]
for i in range(n):
    boolins.append(0)
    
for i in range(m):
    xxx = list(map(int,input().split()))
    if xxx[0] == 1:
        boolins[xxx[1]] = boolins[xxx[1]] + 1
    elif xxx[1] == n :
        boolins[xxx[0]]=boolins[xxx[0]]+ 1
    else:
        None


if 2 in boolins:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def inv(x):
    return pow(x, mod - 2, mod)

def main():
    r1,c1,r2,c2 = LI()

    r = 0
    t1 = 1
    u1 = c2 + 1
    t2 = 1
    u2 = c1
    for i in range(1, r2+2):
        t1 *= u1
        t1 %= mod
        u1 += 1
        ii = inv(i)
        t1 *= ii
        t1 %= mod
        t2 *= u2
        t2 %= mod
        u2 += 1
        t2 *= ii
        t2 %= mod
        if i > r1:
            r += t1 - t2
            r %= mod

    return r

print(main())





### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def inv(x):
    return pow(x, mod - 2, mod)

def main():
    r1,c1,r2,c2 = LI()

    r = 0
    t1 = 1
    u1 = c2 + 1
    t2 = 1
    u2 = c1
    for i in range(1, r2+2):
        t1 *= u1
        t1 %= mod
        u1 += 1
        t1 *= inv(i)
        t1 %= mod
        t2 *= u2
        t2 %= mod
        u2 += 1
        t2 *= inv(i)
        t2 %= mod
        if i > r1:
            r += t1 - t2
            r %= mod

    return r

print(main())
### BUGGY CODE ###

import copy

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

s2 = copy.copy(s)
i = n
j = 0#何個かぶったか
sum2 = 0

for k in range(i):
    #temp = s[k]
    for l in range(i):
        if s[k] == s[l]:
            
            j += 1
            s2.remove(s[k])
           
    if j == 1:
      j = 0
      s2 = [s[k]] + s2
      sum2 += 1
    else:
      #print(j)
      temp = s[k]
        #for m in range(j):
            #s.remove(temp)

      s = [temp]  + copy.copy(s2)
      s2 = copy.copy(s)
      i -= (j-1)
      sum2 += j
      j = 0

    if sum2 == n:
      break
          
sum1 = len(s)
print(sum1)

### FIXED CODE ###

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

s2 = list(set(s))


print(len(s2))
### BUGGY CODE ###

def t(d, a, r, i, c):
  if r[i]!=-1:
    return
  r[i]=c
  for aj in a[i]:
    t(d, a, r, aj, (c+d[i][aj])%2)

N, = list(map(int, input().split()))
d = []
for i in range(N):
  d.append([-1 for j in range(N)])
a = [[] for i in range(N)]
for i in range(N-1):
  u, v, w = list(map(int, input().split()))
  u -= 1
  v -= 1
  d[u][v] = w%2
  d[v][u] = w%2
  a[u].append(v)
  a[v].append(u)
r = [-1 for i in range(N)]
t(d, a, r, 0, 0)
for i in range(N):
  print(r[i])

### FIXED CODE ###

N, = list(map(int, input().split()))
a = [{} for i in range(N)]
for i in range(N-1):
  u, v, w = list(map(int, input().split()))
  u -= 1
  v -= 1
  a[u][v] = w%2
  a[v][u] = w%2
r = [-1 for i in range(N)]
r[0] = 0
q = [0]
while q:
  i = q.pop(0)
  for aj in a[i].keys():
    if r[aj]==-1:
      r[aj] = (r[i]+a[i][aj])%2
      q.append(aj)
for i in range(N):
  print(r[i])
### BUGGY CODE ###

def main():
    from collections import Counter as ct
    n = int(input())
    a = ct(list(map(int, input().split())))
    a2 = sorted([i for i, j in a.items() if j == 1])
    a3 = sorted([i for i, j in a.items() if j > 1])

    s = set()
    ans = 0
    for i in a3:
        for j in s:
            if i % j == 0:
                break
        else:
            s.add(i)
    for i in a2:
        for j in s:
            if i % j == 0:
                break
        else:
            ans += 1
            s.add(i)
    print(ans)


main()


### FIXED CODE ###


def main():
    from collections import Counter as ct
    n = int(input())
    s = list(map(int, input().split()))
    a = ct(s)
    a2 = sorted([i for i, j in a.items() if j == 1])
    a3 = sorted([i for i, j in a.items() if j > 1])
    s = set(s)

    ans = 0
    for i in a3:
        if i in s:
            k = i
            while k <= 10**6:
                if k in s:
                    s.remove(k)
                k += i
    for i in a2:
        if i in s:
            ans += 1
            k = i
            while k <= 10**6:
                if k in s:
                    s.remove(k)
                k += i
    print(ans)


main()
### BUGGY CODE ###

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0
def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
s=list(input())
mod=10**9+7
K=modinv(10,13)
dp=[[0 for k in range(13)] for i in range(len(s))]
#dp[i][j]=初めのindex=i番目まで見たときに、あまりがjになるような方法の総数
num=s[0]
if s[0]=="?":
    for i in range(10):
        dp[0][i]=1
else:
    number=int(s[0])
    dp[0][number]=1

for i in range(1,len(s)):
    if s[i]=="?":
        for k in range(13):
            for j in range(10):
                dp[i][k]+=dp[i-1][((k-j)*K)%13]
        dp[i][k]=dp[i][k]%mod
    else:
        number=int(s[i])
        for k in range(13):
            dp[i][k]=dp[i-1][((k-number)*K)%13]%mod
print(dp[len(s)-1][5]%mod)

### FIXED CODE ###

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0
def modinv(a, m):
    g, x, y = xgcd(a, m)
    return x % m
def main():
    s=list(input())
    mod=10**9+7
    K=modinv(10,13)
    U=[[0 for i in range(10) ]for k in range(13)]
    for i in range(13):
        for j in range(10):
            U[i][j]=((i-j)*K)%13

    dp=[[0 for k in range(13)] for i in range(len(s))]
    #dp[i][j]=初めのindex=i番目まで見たときに、あまりがjになるような方法の総数
    num=s[0]
    if s[0]=="?":
        for i in range(10):
            dp[0][i]=1
    else:
        number=int(s[0])
        dp[0][number]=1

    for i in range(1,len(s)):
        for k in range(13):
            if s[i]=="?":
                for j in range(10):
                    dp[i][k]+=dp[i-1][U[k][j]]%mod
            else:
                number=int(s[i])
                dp[i][k]=dp[i-1][U[k][number]]%mod
    print(dp[len(s)-1][5]%mod)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

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

xy = []

while N >= 2:
    if A[-2] > 0:
        y = A.pop()
        x = A.pop(0)

        xy.append([x,y])

        A = [x-y] + A

    else:
        x = A.pop()
        y = A.pop(0)

        xy.append([x,y])

        A.append(x-y)
    
    N -= 1

print(A[0])
for x, y in xy:
    print(x,y)

### FIXED CODE ###

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

xy = [0]*(N-1)
idx = 0

n = A.pop()

for i in range(N-1):
    a = A.pop()
    if a > 0:
        xy[idx] = [A[0], a]
        A[0] -= a
    else:
        xy[idx] = [n, a]
        n -= a
        idx += 1
        for j in A:
            xy[idx] = [n, j]
            n -= j
            idx += 1
        break

    idx += 1

print(n)
for x, y in xy:
    print(x,y)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
h,w,m=map(int, input().split())
from collections import defaultdict
hd=defaultdict(int)
wd=defaultdict(int)
hd2=defaultdict(list)
for i in range(m):
    h0,w0=map(int, input().split())
    hd[h0]+=1
    hd2[h0].append(w0)
    wd[w0]+=1

max_h_list = [kv[0] for kv in hd.items() if kv[1] == max(hd.values())]
max_w_list = [kv[0] for kv in wd.items() if kv[1] == max(wd.values())]

ans=float('inf')


for x in max_h_list:
    hlist=hd2[x]
    for y in max_w_list:
        if y in hlist:
            ans=min(ans,1)
        else:
            ans=min(ans,0)
print(hd[max_h_list[0]]+wd[max_w_list[0]]-ans)


### FIXED CODE ###

import sys
from collections import defaultdict
input = sys.stdin.readline
h,w,m=map(int, input().split())
hd=[0 for i in range(h+1)]
wd=[0 for i in range(w+1)]
hw=defaultdict(int)
hmax=0
wmax=0
for i in range(m):
    h0,w0=map(int, input().split())
    hd[h0]+=1
    hmax=max(hmax,hd[h0])
    wd[w0]+=1
    wmax=max(wmax,wd[w0])
    hw[(h0,w0)]+=1

max_h_list=[]
max_w_list=[]
for k in range(h+1):
    if hd[k]==hmax:
        max_h_list.append(k)

for k in range(w+1):
    if wd[k]==wmax:
        max_w_list.append(k)

ans=float('inf')

for x in max_h_list:
    for y in max_w_list:
        if hw[(x,y)]==1:
            ans=min(ans,1)
        else:
            ans=min(ans,0)
            break
print(hmax+wmax-ans)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
lr = [list(map(int, input().split())) for i in range(q)]
count = 0

for i in range(q):
    s_extra = s[(lr[i][0] - 1):lr[i][1]]
    print(s_extra.count("AC"))

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
lr = [list(map(int, input().split())) for i in range(q)]
s_count = [0 for i in range(n + 1)]
for i in range(n):
    s_count[i + 1] = s_count[i] + (1 if s[i:i + 2] == 'AC' else 0)

for i in range(q):
    print(s_count[lr[i][1] - 1] - s_count[lr[i][0] - 1])
### BUGGY CODE ###

n = int(input())
import numpy as np
cnt = 0
for i in range(1,n+1):
    for j in range(1,n+1):
        l = np.gcd(i,j)
        for k in range(1,n+1):
            if i==1 or j==1 or k==1:
                cnt += 1
            else:
                cnt += np.gcd(k,l)
print(cnt)

### FIXED CODE ###

from math import gcd
ans = 0
n = int(input())

for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            l = gcd(i,j)
            ans += gcd(k,l)
print(ans)
### BUGGY CODE ###

n = int(input())
ans = 0
for i in range(n):
    ans += i
print(ans)

### FIXED CODE ###

n = int(input())
ans = 0
print(n*(n-1)//2)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split(' ')))
result = []
for i in range(n):
    result.append(a.index(i+1)+1)
print(*result)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split(' ')))
result = [(a[i], i) for i in range(n)]
result.sort()
out = [result[i][1]+1 for i in range(n)]
print(*out)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n=int(input())
uvw=[list(map(int,input().split())) for i in range(n-1)]

#グラフの連結成分を調べる
def Graph(ab):
    G=[[] for i in range(n)]
    #up_G=[0]*n#up_G[i]=頂点iの親
    for a,b,c in ab:
        G[a-1].append((b,c))
        G[b-1].append((a,c))
    return G

#木上のDFSテンプレ
from collections import deque
def dfs(G,v,p):
    q=deque([])
    q.append([v,p])
    dis=0
    dis_l=[-1]*n
    dis_l[0]=0
    while q:
        V,P=q[-1]
        for new_v in G[V-1]:
            v0,v1=new_v
            #new_vが頂点の時はアウト
            if v0==P:continue
            if dis_l[v0-1]>=0:continue
            dis=dis_l[V-1]+v1
            dis_l[v0-1]=dis
            q.append([v0,V])
            break
        else:
            q.pop()
    return dis_l


log=Graph(uvw)
ans=dfs(log,1,-1)

for i in ans:
    if i%2==0:
        print(0)
    else:
        print(1)

### FIXED CODE ###

import sys
input=sys.stdin.readline
n=int(input())

#グラフの連結成分を調べる
def Graph():
    G=[[] for i in range(n)]
    #up_G=[0]*n#up_G[i]=頂点iの親
    for i in range(n-1):
        a,b,c=map(int,input().split())
        c=0 if c%2==0 else 1
        G[a-1].append((b,c))
        G[b-1].append((a,c))
    return G

#木上のDFSテンプレ
from collections import deque
def dfs(G,v,p):
    q=deque()
    q.append((v,p))
    dis=0
    dis_l=[-1]*n
    dis_l[0]=0
    while q:
        V,P=q.pop()
        for new_v in G[V-1]:
            v0,v1=new_v
            #new_vが頂点の時はアウト
            if v0==P:continue
            if dis_l[v0-1]>=0:continue
            dis=(dis_l[V-1]+v1)%2
            dis_l[v0-1]=dis
            q.append((v0,V))

    return dis_l


log=Graph()
ans=dfs(log,1,-1)
print(*ans,sep='\n')