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

class Combination:
    '''MOD上の
    計算量：階乗・逆元テーブルの作成O(N)
    nCkを求めるO(1)'''

    def __init__(self, n, MOD):
        self.fact = [1] * (n + 1)
        for i in range(1, n + 1):
            self.fact[i] = self.fact[i-1] * i % MOD
        self.inv_fact = [pow(self.fact[i], MOD - 2, MOD) for i in range(n + 1)]
        self.MOD = MOD

    def factorial(self, k):
        """k!を求める O(1)"""
        return self.fact[k]

    def inverse_factorial(self, k):
        """k!の逆元を求める O(1)"""
        return self.inv_fact[k]

    def permutation(self, k, r):
        """kPrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[r]) % self.MOD

    def combination(self, k, r):
        """kCrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD


h, w, n = map(int, input().split())
info = [(1, 1)] + [tuple(map(int, input().split())) for i in range(n)] + [(h, w)]
n += 2
MOD = 10**9 + 7
comb = Combination(w+h+1, MOD)

dp = {}
dp[0] = (0, 1)
def solve(ind):
    if ind in dp:
        return dp[ind]
    i, j = info[ind]
    dp0 = 0
    dp1 = 0
    for ind2 in range(n):
        if ind2 == ind:
            continue
        pi, pj = info[ind2]
        if pi <= i and pj <= j:
            tmp = comb.combination((i+j)-(pi+pj), i-pi)
            dp0 += tmp * solve(ind2)[1] % MOD
            dp1 += tmp * solve(ind2)[0] % MOD
    dp[ind] = (dp0, dp1)
    return dp[ind]

for i in range(n):
    solve(i)
print((dp[n-1][0] - dp[n-1][1]) % MOD)


### FIXED CODE ###

class Combination:
    def __init__(self, n, MOD):
        self.fact = [1] * (n + 1)
        for i in range(1, n + 1):
            self.fact[i] = self.fact[i-1] * i % MOD
        self.inv_fact = [pow(self.fact[i], MOD - 2, MOD) for i in range(n + 1)]
        self.MOD = MOD

    def factorial(self, k):
        """k!を求める O(1)"""
        return self.fact[k]

    def inverse_factorial(self, k):
        """k!の逆元を求める O(1)"""
        return self.inv_fact[k]

    def permutation(self, k, r):
        """kPrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[r]) % self.MOD

    def combination(self, k, r):
        """kCrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD


h, w, n = map(int, input().split())
info = [(1, 1)] + [tuple(map(int, input().split())) for i in range(n)] + [(h, w)]
info = sorted(info)
n += 2
MOD = 10**9 + 7
comb = Combination(w+h+1, MOD)

dp = {}
dp[0] = (0, 1)
def solve(ind):
    if ind in dp:
        return dp[ind]
    i, j = info[ind]
    dp0 = 0
    dp1 = 0
    for ind2 in range(n):
        if ind2 == ind:
            continue
        pi, pj = info[ind2]
        if pi <= i and pj <= j:
            tmp = comb.combination((i+j)-(pi+pj), i-pi)
            dp0 += tmp * solve(ind2)[1] % MOD
            dp1 += tmp * solve(ind2)[0] % MOD
    dp[ind] = (dp0, dp1)
    return dp[ind]

for i in range(n):
    solve(i)
print((dp[n-1][0] - dp[n-1][1]) % MOD)
### BUGGY CODE ###

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

score=[0]*n
for i in range(q):
    p,x=map(int,input().split())
    update_n = [p-1]
    while update_n:
        current_n = update_n.pop(0)
        score[current_n] += x
        update_n += edge[current_n]
print(*score)

### FIXED CODE ###

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

base_score = [0]*n
for i in range(q):
    p,x=map(int,input().split())
    base_score[p-1] += x
    
score=[0]*n

for i,bs in enumerate(base_score):
    score[i] = bs
    for j in edge[i]:
        base_score[j] += bs

print(*score)
### BUGGY CODE ###

N=int(input())
S=[a for a in range(1,N)]
print(sum(S))


### FIXED CODE ###

N=int(input())
print((N*(N-1)//2))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
H, W, K = list(map(int, input().split()))

choco = []
for i in range(H):
  s = input().strip()
  a = list(map(int, list(s)))
  choco.append(a)

def f(n):
  if n == 1:
    return [[0], [1]]
  a = f(n-1)
  na = []
  for v in a:
    na.append([0] + v)
    na.append([1] + v)
  return na

def min_split(h):
  sum_cnt = [0] * H
  num_split = 0
  for j in range(W):
    c = 0
    cnt = [0] * H
    for i in range(H):
      if choco[i][j] == 1:
        cnt[c] += 1
      if i < H-1 and h[i] == 1:
        c += 1
    new_cnt = [x + y for x, y in zip(sum_cnt, cnt)]
    if max(new_cnt) > K:
      num_split += 1
      sum_cnt = cnt
    else:
      sum_cnt = new_cnt
  return num_split + sum(h)

min_m = float('inf')
for h in f(H-1):
  m = min_split(h)
  min_m = min(min_m, m)
print(min_m)

### FIXED CODE ###

import sys, itertools
input = sys.stdin.readline
H, W, K = list(map(int, input().split()))

choco = []
for i in range(H):
  s = input().strip()
  a = list(map(int, list(s)))
  choco.append(a)

def min_split(h):
  sum_cnt = [0] * H
  num_split = 0
  for j in range(W):
    c = 0
    cnt = [0] * H
    flag = False
    for i in range(H):
      if choco[i][j] == 1:
        cnt[c] += 1
        if cnt[c] > K:
          return float('inf')
        if cnt[c] + sum_cnt[c] > K:
          flag = True
      if i < H-1 and h[i] == 1:
        c += 1
    if flag:
      num_split += 1
      sum_cnt = cnt
    else:
      for i in range(len(cnt)):
      	sum_cnt[i] += cnt[i]
  return num_split + sum(h)

min_m = float('inf')
for h in itertools.product([0,1], repeat=H-1):
  m = min_split(h)
  min_m = min(min_m, m)
print(min_m)
### BUGGY CODE ###

n, k = [int(i) for i in input().split(' ')]
P = [int(i) for i in input().split(' ')]

ans_ind = max([sum(P[i:i+k]) for i in range(len(P)-(k-1))])
ans = (ans_ind + k) * 0.5

print(ans)

### FIXED CODE ###

n, k = [int(i) for i in input().split(' ')]
P = [int(i) for i in input().split(' ')]

temp = sum(P[:k])
res = temp
for i in range(n- k):
  temp -= P[i]
  temp += P[i+k]
  res = max(res, temp)
  
ans = (res + k) * 0.5

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

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
BC = [list(map(int, input().split())) for i in range(Q)]
for x in BC:
    for y in range(N):
        if A[y] == x[0]:
            A[y] = x[1]
    print(sum(A))


### FIXED CODE ###

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

dictA = {}

for z in A:
    dictA.setdefault(z, 0)
    dictA[z] += 1

sumA = sum(A)

BC = [list(map(int, input().split())) for i in range(Q)]
for x in BC:
    if x[0] in dictA.keys():
        sumA += (x[1] - x[0]) * dictA[x[0]]
        dictA.setdefault(x[1], 0)
        dictA[x[1]] += dictA[x[0]]
        dictA.pop(x[0])
    print(sumA)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

R, C, K = map(int, input().split())
D = dict()
for _ in range(K):
    r, c, v = map(int, input().split())
    D[(r, c)] = v

dp = [[[0] * (C + 1) for _ in range(R + 1)] for _ in range(4)]
for r in range(1, R + 1):
    for c in range(1, C + 1):
        m = max(dp[i][r - 1][c] for i in range(4))
        for n in range(4):
            dp[n][r][c] = max(m, dp[n][r][c - 1])
        if (r, c) in D:
            for n in range(3):
                dp[n + 1][r][c] = max(dp[n + 1][r][c],
                                      m + D[(r, c)],
                                      dp[n][r][c - 1] + D[(r, c)])
print(max(dp[i][-1][-1] for i in range(4)))


### FIXED CODE ###

import sys

input = sys.stdin.readline

R, C, K = map(int, input().split())
D = dict()
for _ in range(K):
    r, c, v = map(int, input().split())
    D[(r, c)] = v

dp0 = [[0] * (C + 1) for _ in range(R + 1)]
dp1 = [[0] * (C + 1) for _ in range(R + 1)]
dp2 = [[0] * (C + 1) for _ in range(R + 1)]
dp3 = [[0] * (C + 1) for _ in range(R + 1)]

for r in range(1, R + 1):
    for c in range(1, C + 1):
        m = max(dp0[r - 1][c], dp1[r - 1][c], dp2[r - 1][c], dp3[r - 1][c])
        dp0[r][c] = max(m, dp0[r][c - 1])
        dp1[r][c] = max(m, dp1[r][c - 1])
        dp2[r][c] = max(m, dp2[r][c - 1])
        dp3[r][c] = max(m, dp3[r][c - 1])
        if (r, c) in D:
            dp1[r][c] = max(dp1[r][c], m + D[(r, c)], dp0[r][c - 1] + D[(r, c)])
            dp2[r][c] = max(dp2[r][c], m + D[(r, c)], dp1[r][c - 1] + D[(r, c)])
            dp3[r][c] = max(dp3[r][c], m + D[(r, c)], dp2[r][c - 1] + D[(r, c)])
print(max(dp0[-1][-1], dp1[-1][-1], dp2[-1][-1], dp3[-1][-1]))
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split(" ")]
q = int(input())

operations = []

for i in range(q):
    temp = input().split(" ")
    operations.append((int(temp[0]), int(temp[1])))

a.sort()

for op in operations:
    target, goto = op

    try:
        index = a.index(target)
        
        while True:
            if a[index] != target:
                break

            a[index] = goto
            index += 1

        print(sum(a))

    except:
        print(sum(a))


### FIXED CODE ###

from collections import defaultdict

d = defaultdict(int)

n = int(input())
a = [int(i) for i in input().split(" ")]
q = int(input())

operations = []

for i in range(q):
    temp = input().split(" ")
    operations.append((int(temp[0]), int(temp[1])))

for hoge in a:
    d[hoge] += 1

initial_sum = 0
for key, value in d.items():
    initial_sum += key * value

for op in operations:
    target, goto = op

    before = goto * d[goto] + target * d[target]
    d[goto] += d[target]
    d[target] = 0

    after = goto * d[goto]
    diff = after - before
    
    initial_sum += diff
    print(initial_sum)
### BUGGY CODE ###

import heapq
from heapq import heapify
n,m = map(int,input().split())
A = list(map(int,input().split()))
#B = [0]*m
#C = [0]*m
#for i in range(m):
#    B[i],C[i] = map(int,input().split())

heapq.heapify(A)
for i in range(m):
    b,c = map(int,input().split())
    for i in range(b):
        if A[0]<c:
            heapq.heapreplace(A,c)
        else:
            break
print(sum(A))


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    n,m = map(int,input().split())
    A = list(map(int,input().split()))
    BC = [list(map(int,input().split())) for _ in range(m)]

    BC = sorted(BC,key=lambda x:(x[1]),reverse=True)
    append_list = []
    for b,c in BC:
        if len(append_list)>=n:
            break
        append_list+=[c]*b
    A+=append_list
    A.sort(reverse=True)
    print(sum(A[:n]))
if __name__=='__main__':
    main()
### BUGGY CODE ###

import sys
import math
from fractions import gcd
# import queue
# from collections import Counter
# from itertools import accumulate
# from functools import reduce

def lcm(a, b):
    return a * b // gcd(a, b)

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

big_prime = 1000000007

"""
# 標準入力取得
## 文字列
 =  sys.stdin.readline().rstrip()
 =  list(sys.stdin.readline().rstrip())

## 数値
 =  int(sys.stdin.readline())
 =  map(int, sys.stdin.readline().split())
 =  list(map(int, sys.stdin.readline().split()))
 =  [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""

A, B, K =  map(int, sys.stdin.readline().split())
L = [x for x in range(A, B + 1)]
X = L[:K] + L[len(L) - K::]
for x in sorted(list(set(X))):
    print(x)

### FIXED CODE ###

import sys
import math
from fractions import gcd
# import queue
# from collections import Counter
# from itertools import accumulate
# from functools import reduce

def lcm(a, b):
    return a * b // gcd(a, b)

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

big_prime = 1000000007

"""
# 標準入力取得
## 文字列
 =  sys.stdin.readline().rstrip()
 =  list(sys.stdin.readline().rstrip())

## 数値
 =  int(sys.stdin.readline())
 =  map(int, sys.stdin.readline().split())
 =  list(map(int, sys.stdin.readline().split()))
 =  [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""

A, B, K =  map(int, sys.stdin.readline().split())
X = [x for x in range(A, min(A + K, B + 1))] + [x for x in range(max(B - K + 1, A), B + 1)]
for x in sorted(list(set(X))):
    print(x)
### BUGGY CODE ###

import queue

H,W = map(int, input().split())
#world = [[c for c in input()] for _ in range(H)]
whiteCount = 0

world = []
for i in range(H):
    row = [c for c in input()]
    world.append(row) 
    whiteCount += len([c for c in row if c == '.'])

minRoot = whiteCount + 1

def bfs(x, y, depth, boforeX, beforeY):
    if x == W - 1 and y == H - 1:
        return min(minRoot, depth)

    depth = depth + 1
    appendPosition(x + 1, y, x, y, depth, boforeX, beforeY)
    appendPosition(x - 1, y, x, y, depth, boforeX, beforeY)
    appendPosition(x, y + 1, x, y, depth, boforeX, beforeY)
    appendPosition(x, y - 1, x, y, depth, boforeX, beforeY)

    return minRoot

def appendPosition(newX, newY, currentX, currentY, depth, boforeX, beforeY):
    if newX < 0 or newY < 0 or newX >= W or newY >= H or world[newY][newX] == '#' or (newX == boforeX and newY == beforeY):
        return

    q.put((newX, newY, depth, currentX, currentY))

    
q = queue.Queue()
q.put((0,0,1,-1,-1))

while q.empty() == False:
    position = q.get()
    minRoot = min(minRoot, bfs(*position))

if whiteCount < minRoot:
    print(-1)
else:
    print(whiteCount - minRoot)


### FIXED CODE ###

import queue

H,W = map(int, input().split())
#world = [[c for c in input()] for _ in range(H)]
whiteCount = 0

world = []
for i in range(H):
    row = [c for c in input()]
    world.append(row) 
    whiteCount += len([c for c in row if c == '.'])

minRoot = whiteCount + 1

def bfs(x, y, depth):
    if x == W - 1 and y == H - 1:
        return min(minRoot, depth)

    depth = depth + 1
    appendPosition(x + 1, y, depth)
    appendPosition(x - 1, y, depth)
    appendPosition(x, y + 1, depth)
    appendPosition(x, y - 1, depth)

    return minRoot

def appendPosition(newX, newY, depth):
    if newX < 0 or newY < 0 or newX >= W or newY >= H or world[newY][newX] == '#':
        return

    newPosition = (newX,newY)
    if newPosition in visitedPosition:
        return

    q.put((newX, newY, depth))
    visitedPosition.add(newPosition)

q = queue.Queue()
q.put((0,0,1))
visitedPosition = set()
visitedPosition.add((0,0))

while q.empty() == False:
    position = q.get()
    minRoot = min(minRoot, bfs(*position))

if whiteCount < minRoot:
    print(-1)
else:
    print(whiteCount - minRoot)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)

def intinput(): return map(int,sys.stdin.readline().split())

fib=[0,1,1]
for i in range(3,100003):
    fib.append(fib[i-1]+fib[i-2])

n,m=intinput()
mod=10**9+7
a=[int(sys.stdin.readline()) for _ in range(m)]
k=1
y=1
for i in range(n):
    if i in a:
        k*=fib[y-1]
        y=0
    y+=1
k*=fib[y]
print(k%mod)

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

def intinput(): return map(int,sys.stdin.readline().split())

fib={0:0,1:1,2:1}
for i in range(3,100003):
    fib[i]=fib[i-1]+fib[i-2]
  #  fib.append(fib[i-1]+fib[i-2])

n,m=intinput()
mod=10**9+7
a=[int(sys.stdin.readline()) for _ in range(m)]
if m!=0:
    l=[a[0]]
    for i in range(len(a)-1):
        l.append(a[i+1]-a[i]-1)
    l.append(n-a[-1])
    k=1
    for i in l:
        k=fib[i]*k%mod
    print(k%mod)
else:
    print(fib[n+1]%mod)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n,w=map(int,input().split())
dp=[[0]*w for _ in range(n)]
for i in range(n):
  a,b=map(int,input().split())
  for j in range(w):
    if i==0:
      if j>a-2:dp[i][j]=b
    elif j>a-2:
      if j==a-1:dp[i][j]=max(b,dp[i-1][j])
      else:dp[i][j]=max(dp[i-1][j-a]+b,dp[i-1][j])
    else:dp[i][j]=dp[i-1][j]
print(dp[n-1][w-1])

### FIXED CODE ###

n,w=map(int,input().split())
dp=[[0]*w for _ in range(n)]
for i in range(n):
  a,b=map(int,input().split())
  for j in range(w):
    if i==0:
      if j>a-2:dp[i][j]=b
    elif j>a-2:
      if j==a-1:dp[i][j]=max(b,dp[i-1][j])
      else:dp[i][j]=max(dp[i-1][j-a]+b,dp[i-1][j])
    else:dp[i][j]=dp[i-1][j]
print(dp[-1][-1])
### BUGGY CODE ###

import math
from functools import reduce

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

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

k = int(input())
result = 0
for x in range(1,k+1):
    for y in range(1,k+1):
        for z in range(1,k+1):
            result += gcd(x,y,z)
print(result)


### FIXED CODE ###

import math
from functools import reduce

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

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

k = int(input())
result = 0
for x in range(1,k+1):
    for y in range(1,k+1):
        for z in range(1,k+1):
            result += gcd(x,y,z)
print(result)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import math
def main():
    N,M = map(int,input().split())
    A = list(map(int,input().split()))
    for _ in range(M):
        A[A.index(max(A))] = math.floor(A[A.index(max(A))]-(max(A)/2))
    print(sum(A))
if __name__ == '__main__':
    main()

### FIXED CODE ###

# -*- coding: utf-8 -*-
import heapq as hq
def main():
    N,M = map(int,input().split())
    A=[-int(j) for j in input().split()]
    hq.heapify(A)
    for _ in range(M):
        tmp = hq.heappop(A)
        hq.heappush(A,(-((-tmp)//2)))
    print(-sum(A))
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
X, Y, U = [], [], []
if True:
    H, W, *nums = map(int, sys.stdin.read().split())
    i = 0
    for _ in range(H):
        X.append(nums[i:i + W])
        i += W
        U.append([set() for _ in range(W)])
    for _ in range(H):
        Y.append(nums[i:i + W])
        i += W
else:
    H, W = map(int, input().split())
    for _ in range(H):
        X.append(list(map(int, input().split())))
        U.append([set() for _ in range(W)])
    for _ in range(H):
        Y.append(list(map(int, input().split())))

U[0][0] = set([ abs(X[0][0] - Y[0][0]) ])

for i in range(W):
    for j in range(H):
        for k in U[j][i]:
            if j + 1 < H:
                x = abs(X[j + 1][i] - Y[j + 1][i])
                U[j + 1][i].update([abs(k + x), abs(k - x)])
            if i + 1 < W:
                x = abs(X[j][i + 1] - Y[j][i + 1])
                U[j][i + 1].update([abs(k + x), abs(k - x)])
print(min(U[-1][-1]))

### FIXED CODE ###

# at ABC 147 e (500)
import sys
X, Y, U = [], [], []
if True:
    H, W, *nums = map(int, sys.stdin.read().split())
    i = 0
    for _ in range(H):
        X.append(nums[i:i + W])
        i += W
        U.append([0] * W)
    for _ in range(H):
        Y.append(nums[i:i + W])
        i += W
else:    
    H, W = map(int, input().split())
    for _ in range(H):
        X.append(list(map(int, input().split())))
        U.append([0 for _ in range(W)])
    for _ in range(H):
        Y.append(list(map(int, input().split())))

mid = 80*80

init = abs(X[0][0] - Y[0][0])
U[0][0] = (1 << (mid - init)) | (1 << (mid + init))

for i in range(W):
    for j in range(H):
        k = abs(X[j][i] - Y[j][i])
        if j > 0:
            U[j][i] |= (U[j - 1][i] << k)
            U[j][i] |= (U[j - 1][i] >> k)
        if i > 0:
            U[j][i] |= (U[j][i - 1] << k)
            U[j][i] |= (U[j][i - 1] >> k)
#        U[j][i] = U[j][i] & ((1 << (2 * mid)) - 1)
    
i = 0
min_ = float("inf")
while True:
     if U[-1][-1] & 1:
         min_ = min(min_, abs(i - mid))
     U[-1][-1] = U[-1][-1] >> 1
     i += 1
     if i >= 2 * mid:
         break
print(min_)
### BUGGY CODE ###

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

ans = 3*10**5
for i in range(N):
    cnt = 0
    # 基準より左側の人
    for j in range(i):
        if S[j] == "W":
            cnt += 1
    # 基準より右側の人
    for k in range(1,N-i):
        if S[i+k] == "E":
            cnt += 1
    if ans > cnt:
        ans = cnt
print(ans)


### FIXED CODE ###

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

cnt = [0] * N
if S[0] == "W":
    cnt[0] = 1

for i in range(1, N):
    if S[i] == "W":
        cnt[i] = cnt[i-1] + 1
    else:
        cnt[i] = cnt[i-1]

ans = 3*10**5
for i in range(N):
    temp = 0
    # 基準より左側の人
    if i != 0:
        temp += cnt[i-1]
    # 基準より右側の人
    if i != N-1:
        temp = temp + ((N-1) - i) - (cnt[N-1] - cnt[i])
    if ans > temp:
        ans = temp
print(ans)
### BUGGY CODE ###

import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)
K=int(input())
c = 0
for i in range(1,K+1):
  for j in range(1,K+1):
    for k in range(1,K+1):
      c += gcd(i, j, k)
print(c)

### FIXED CODE ###

import math
K=int(input())
c = 0
for i in range(1,K+1):
  for j in range(1,K+1):
    if math.gcd(i,j) == 1:
      c += K
    else:
      for k in range(1,K+1):
        if i == j == k:
          c += i
        elif i == j:
          c += math.gcd(i,k)
        elif i == k:
          c += math.gcd(i,j)
        elif j == k:
          c += math.gcd(i,k)
        else:
          c += math.gcd(math.gcd(i, j), k)
print(c)
### BUGGY CODE ###

def SPFA(G: list, source=0):
	from collections import deque
	V = len(G)
	d = [float("inf")] * V
	inQ = [False] * V
	cnt = [0] * V
	d[source] = 0
	cnt[source] = 1
	Q = deque([source])
	while Q:
		f = Q.popleft()
		inQ[f] = False
		for t, c in G[f]:
			dist = d[f] + c
			if dist < d[t]:
				d[t] = dist
				if not inQ[t]:
					Q.append(t)
					inQ[t] = True
					cnt[t] += 1
					front = Q.popleft()
					if d[front] > dist:
						Q.append(front)
					else:
						Q.appendleft(front)
				if cnt[t] > V:
					# negative cycle
					return None
	return d


def main():
	n, m, *L = map(int, open(0).read().split())
	con = [[] for _ in range(n)]
	g = []
	c = [True] * n
	for s, t in zip(*[iter(L)] * 2):
		con[s - 1] += [(t - 1, - 1)]
		c[t - 1] = False
	for i in range(n):
		if c[i]:
			root = i
			break
	dist = SPFA(con, root)
	ans = [0] * n
	for s, t in zip(*[iter(L)] * 2):
		if dist[t - 1] == dist[s - 1] - 1:
			ans[t - 1] = s
	print("\n".join(map(str, ans)))

if __name__ == "__main__":
	main()


### FIXED CODE ###

def topologicalSort(g: list, deg: list):
	ret = []
	q = []
	for i, d in enumerate(deg):
		if not d:
			ret.append(i)
			q.append(i)
	while q:
		cur = q.pop(0)
		for nxt in g[cur]:
			deg[nxt] -= 1
			if not deg[nxt]:
				ret.append(nxt)
				q.append(nxt)
	return ret

def main():
	v, e, *L = map(int, open(0).read().split())
	g = [[] for _ in range(v)]
	rev = [[] for _ in range(v)]
	deg = [0] * v
	for s, t in zip(*[iter(L)] * 2):
		g[s - 1].append(t - 1)
		rev[t - 1].append(s - 1)
		deg[t - 1] += 1
	order = topologicalSort(g, deg)
	idx = [None] * v
	for i, o in enumerate(order):
		idx[o] = i
	ans = [0] * v
	for i in range(v):
		if rev[i]:
			ans[i] = max(rev[i], key=lambda x: idx[x]) + 1
	print("\n".join(map(str, ans)))

if __name__ == "__main__":
	main()