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

N, W, H = [int(x) for x in input().split()]

map_x = [False] * W
count_x = 0
map_y = [False] * H
count_y = 0

wifi_x = []
wifi_y = []
for _ in range(N):
    x, y, w = [int(x) for x in input().split()]
    wifi_x.append((x - w, x + w))
    wifi_y.append((y - w, y + w))
wifi_x.sort(key=lambda a: a[1], reverse=True)
wifi_y.sort(key=lambda a: a[1], reverse=True)


def check_wifi(wifi, l):
    for x1, x2 in wifi:
        if x1 <= l < x2:
            return x2
    return None


ans_x = True
b = 0
for x in range(W):
    if x < b:
        continue

    b = check_wifi(wifi_x, x)
    if not b:
        ans_x = False
        break

if not ans_x:
    b = 0
    for y in range(H):
        if y < b:
            continue

        b = check_wifi(wifi_y, y)
        if not b:
            print('No')
            exit()

print('Yes')

### FIXED CODE ###

N, W, H = [int(x) for x in input().split()]

map_x = [0] * W
map_y = [0] * H

for _ in range(N):
    x, y, w = [int(x) for x in input().split()]
    mx = max(0, x - w)
    map_x[mx] = max(map_x[mx], x + w - mx)
    my = max(0, y - w)
    map_y[my] = max(map_y[my], y + w - my)


def check_wifi(wifi):
    m = 0
    end = len(wifi)

    for i, x in enumerate(wifi):
        if x and i + x > m:
            m = i + x

        if m >= end:
            return True

        if i < m:
            continue

        return False

    return False


print('Yes' if check_wifi(map_x) or check_wifi(map_y) else 'No')
### BUGGY CODE ###

N = int(input())
A = []
while 1:
    A.append(N%10)
    N = N//10
    if N == 0:
        break

if sum(A)%9==0:print("Yes")
else:print("No")

### FIXED CODE ###

A = list(input())
for n in range(len(A)):
    A[n] = int(A[n])

if sum(A)%9==0:print("Yes")
else:print("No")
### BUGGY CODE ###

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())

s = [list(input()) for _i in range(h)]

bord = [[float('inf') for _i in range(w)] for _j in range(h)]
bord[ch-1][cw-1] = 0

dh, dw = dh-1, dw-1
from collections import deque
q = deque([[ch-1, cw-1]])
while q:
    x, y = q.popleft()
    for i, j in [[1,0], [0, 1], [-1, 0], [0, -1]]:
        if 0 <= x+i and 0 <= y+j and x+i < h and y+j < w:
            if s[x+i][y+j]=='.':
                if bord[x][y] < bord[x+i][y+j]:
                    bord[x+i][y+j] = bord[x][y]
                    q.appendleft([x+i, y+j])
            else:
                for n in range(-2, 3):
                    for m in range(-2, 3):
                        if n==0 and m==0:
                            continue
                        if 0 <= x+n and 0 <= y+m and x+n < h and y+m < w:
                            if s[x+n][y+m] == '.':
                                if bord[x][y]+1 < bord[x+n][y+m]:
                                    bord[x+n][y+m] = bord[x][y] + 1
                                    q.appendleft([x+n, y+m])

if bord[dh][dw]==float('inf'):
    print(-1)
else:
    print(bord[dh][dw])

### FIXED CODE ###

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())

s = [list(input()) for _i in range(h)]

bord = [[float('inf') for _i in range(w)] for _j in range(h)]
bord[ch-1][cw-1] = 0

dh, dw = dh-1, dw-1
from collections import deque
q = deque([[ch-1, cw-1]])
while q:
    x, y = q.pop()
    for i, j in [[1,0], [0, 1], [-1, 0], [0, -1]]:
        if 0 <= x+i and 0 <= y+j and x+i < h and y+j < w:
            if s[x+i][y+j]=='.':
                if bord[x][y] < bord[x+i][y+j]:
                    bord[x+i][y+j] = bord[x][y]
                    q.append([x+i, y+j])
            else:
                for n in range(-2, 3):
                    for m in range(-2, 3):
                        if n==0 and m==0:
                            continue
                        if 0 <= x+n and 0 <= y+m and x+n < h and y+m < w:
                            if s[x+n][y+m] == '.':
                                if bord[x][y]+1 < bord[x+n][y+m]:
                                    bord[x+n][y+m] = bord[x][y] + 1
                                    q.appendleft([x+n, y+m])

if bord[dh][dw]==float('inf'):
    print(-1)
else:
    print(bord[dh][dw])
### BUGGY CODE ###

import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# rstrip().decode('utf-8')
# INF=float("inf")
#MOD=10**9+7
# sys.setrecursionlimit(2147483647)
# import math
#import numpy as np
# import operator
import bisect
# from heapq import heapify,heappop,heappush
#from math import gcd
# from fractions import gcd
#from collections import deque
#from collections import defaultdict
# from collections import Counter
#from itertools import accumulate
# from itertools import groupby
# from itertools import permutations
# from itertools import combinations
# from scipy.sparse import csr_matrix
# from scipy.sparse.csgraph import floyd_warshall
# from scipy.sparse.csgraph import csgraph_from_dense
# from scipy.sparse.csgraph import dijkstra
# map(int,input().split())


def main():
	n,*p=map(int,read().split())
	H=[0,0,n+1,n+1]
	pidx=[0]*(n+1)
	for i in range(n):
		pidx[p[i]]=i+1
	
	pidx.reverse()
	
	
	ans=0
	for i in pidx:
		I=bisect.bisect_left(H,i)
		ans+=p[i-1]*((H[I-1]-H[I-2])*(H[I]-i)+(H[I+1]-H[I])*(i-H[I-1]))
		H.insert(I,i)
	print(ans)
	
	
if __name__ == "__main__":
		main()


### FIXED CODE ###

import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# rstrip().decode('utf-8')
# INF=float("inf")
#MOD=10**9+7
# sys.setrecursionlimit(2147483647)
# import math
#import numpy as np
# import operator
import bisect
# from heapq import heapify,heappop,heappush
#from math import gcd
# from fractions import gcd
#from collections import deque
#from collections import defaultdict
# from collections import Counter
#from itertools import accumulate
# from itertools import groupby
# from itertools import permutations
# from itertools import combinations
# from scipy.sparse import csr_matrix
# from scipy.sparse.csgraph import floyd_warshall
# from scipy.sparse.csgraph import csgraph_from_dense
# from scipy.sparse.csgraph import dijkstra
# map(int,input().split())


def main():
	n,*p=map(int,read().split())
	H=[0,0,n+1,n+1]
	pidx=[0]*(n+1)
	for i in range(n):
		pidx[p[i]]=i+1
	
	pidx.reverse()
	
	
	ans=0
	for i in pidx:
		I=bisect.bisect_left(H,i)
		ans+=p[i-1]*((H[I-1]-H[I-2])*(H[I]-i)+(H[I+1]-H[I])*(i-H[I-1]))
		H.insert(I,i)
	print(ans)
	
	
if __name__ == "__main__":
		main()
### BUGGY CODE ###

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

INF = 10**10

h,n = nm()

dp = [INF] * (h+1)

dp[0] = 0

for i in range(n):
  a,b = nm()

  for j in range(h):
    nj = min(j+a,h) 
    dp[nj]=min(dp[nj],dp[j]+b) # ダメージがj+aの時のコスト

print(dp[h])


### FIXED CODE ###

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

INF = 10**10

h,n = nm()

dp = [INF] * (h+1)

dp[0] = 0

for i in range(n):
  a,b = nm()

  for j in range(h):
    nj = min(j+a,h) 
    dp[nj]=min(dp[nj],dp[j]+b) # ダメージがj+aの時のコスト

print(dp[h])
### BUGGY CODE ###

a,b,c=map(int,input().split())
e=0
f=[[1,1]]
k=[[1,1,1],[2,1,1,1,2],[3,2,2,1,2,2,3],[5,3,3,2,4,2,3,3,5],[8,5,5,3,6,4,6,3,5,5,8],[12,8,8,5,10,6,9,6,10,5,8,8,12],[21,13,13,8,16,10,15,9,15,10,16,8,13,13,21]]
if b==1:
    print(1)
else:
    d=k[b-2]
    for i in range(0,a):
        l=len(f)
        for j in range(0,l):
            f.append([f[j][0],f[j][1]*d[2*(f[j][0]-1)]])
            if f[j][0]-1>0 and f[j][0]-1>=c-(a-i):
                f.append([f[j][0]-1,f[j][1]*d[1+2*(f[j][0]-2)]])
            if f[j][0]+1<=b and f[j][0]+1<=c+(a-i):
                f.append([f[j][0]+1,f[j][1]*d[2*(f[j][0]-1)+1]])
            j+=1
        else:
            del f[:l]
    else:
        for i in range(0,len(f)):
            if f[i][0]==c:
                e+=f[i][1]
        print(e%(10**9+7))

### FIXED CODE ###

a,b,c=map(int,input().split())
s=[[0]*b for i in range(a+1)]
s[0][0]=1
k=[[1,1,1],[2,1,1,1,2],[3,2,2,1,2,2,3],[5,3,3,2,4,2,3,3,5],[8,5,5,3,6,4,6,3,5,5,8],[13,8,8,5,10,6,9,6,10,5,8,8,13],[21,13,13,8,16,10,15,9,15,10,16,8,13,13,21]]
if b==1:
    print(1)
elif c-a>=2:
    print(0)    
else:
    d=k[b-2]
    for i in range(1,a+1):
        s[i][b-1]=s[i-1][b-1]*d[2*(b-1)]+s[i-1][b-2]*d[2*(b-1)-1]
        for j in range(0,b-1):
            if j==0:
                s[i][0]=s[i-1][0]*d[0]+s[i-1][1]*d[1]
            else:    
                s[i][j]=s[i-1][j-1]*d[2*j-1]+s[i-1][j]*d[2*j]+s[i-1][j+1]*d[2*j+1]
    print(s[a][c-1]%(10**9+7))
### BUGGY CODE ###

import copy
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
  
def main():
  n = int(input())
  arr = list(map(int, input().split()))
  prime = primes(max(arr))
  pf = isPair(prime, arr)
  sf = isSet(prime, arr)
  

  if pf and sf:
    print('pairwise coprime')
    exit()
  if not sf:
    print('not coprime')
    exit()
  else:
    print('setwise coprime')
    exit()

def isPair(prime, arr):
  searched = []
  for p in prime:
    for a in arr:
      if a % p == 0:
        if p in searched:
          return False
        searched += [p]
  return True

def isSet(prime, arr):
  searched = []
  for p in prime:
    if arr[0] % p == 0:
      searched.append(p)
      
  for a in arr[1:]:
    if len(searched) == 0:
      return True
    tmp = []
    for s in searched:
      if a % s == 0:
        tmp.append(s)
        
    searched = tmp
  if len(searched) == 0:
      return True
  return False
  
  
main()

### FIXED CODE ###

import math
from functools import reduce

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

def factorize(n, d):
  # if n == 0 or n == 1:
    # return []
    arr = []
    tmp = n
    while True:
      i = d[tmp]
      if i == 1:
        break
      #cnt=0
      while tmp%i==0:
        #cnt+=1
        tmp //= i
      arr.append(i)
    if tmp!=1:
      arr.append(tmp)
    if arr==[]:
      arr.append(n)
    return arr

def minimum_prime(n):
  # 試し割りをする際の最小の素数
  # エラトステネスの篩と同様の実装
    d = list(range(n+1))
    d[0] = 1
    for i in range(2, int(n**0.5) + 1):
        if d[i] != i:
          continue
        for j in range(i * 2, n + 1, i):
          if d[j] == j:
            d[j] = i
    return d  

def main():
  n = int(input())
  arr = list(map(int, input().split()))
  max_arr = max(arr)
  d = minimum_prime(max_arr)
  dp = [0]*(max_arr+1)
  
  if gcd(*arr) != 1:
    print('not coprime')
    exit()
  
  searched = []
  for a in arr:
    if a != 1:
      primes = factorize(a, d)
      for p in primes:
        dp[p] += 1

  if max(dp) < 2:
    print('pairwise coprime')
  else:
    print('setwise coprime')
    

main()
### BUGGY CODE ###

N = int(input())
A = list(map(str, input().split()))
Q = int(input())
S = []
s = sum(map((lambda x: int(x)), A))


for i in range(Q):
    B, C = map(str,input().split())
    if B in A:
        string = ",".join(A)
        string_new = string.replace(B,C)
        A =  string_new.split(",")
        s = sum(map((lambda x: int(x)), A))
        S.append(s)


    else:
        S.append(s)



for s in S:
    print(s)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
S = []
c = 0
s = sum(A)
table = [0] * 100010
# A = pd.Series(A)
# for a in A:
#     print(a)

for i in A:
    table[i] += 1

for i in range(Q):
    B, C = map(int,input().split())
    # if B in A:
    # c = A.count(B)
    c = table[B]
    s += (C - B) * c
    table[C] += table[B]
    table[B] = 0
    # print(s)
        # print((C - B) * c) 
        # string = ",".join(A)
        # string_new = string.replace(B,C)
        # A =  string_new.split(",")
        # s = sum(map((lambda x: int(x)), A))
    S.append(s)

        # A.replace(B, C,c)
        # while B in A:
        #     A[A.index(B)] = C
    # for a in A:
    #     print(a)
    # else:
        # S.append(s)



for s in S:
    print(s)
### BUGGY CODE ###


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

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

for i in range(N):
    x = X[0:i]+X[i+1:]
    x.sort(reverse=True)

#    print(x)
    print( x[((len(x)+1) // 2)-1] )


### FIXED CODE ###


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

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

x = X[:]
x.sort()
m1 = x[N//2 - 1]
m2 = x[N//2]

for a in X:
    if a <= m1:
        print(m2)
    else:
        print(m1)
### BUGGY CODE ###

N,Q=map(int,input().split())
S=input()
LR=[list(map(int,input().split())) for i in range(Q)]
I = []
for i in range(N-1):
  if S[i]=="A" and S[i+1]=="C":
    I.append(1)
  else:
    I.append(0)
      
for i in range(Q):
  l=LR[i][0]-1
  r=LR[i][1]-1
  s=I[l:r]
  print(s.count(1))

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
LR=[list(map(int,input().split())) for i in range(Q)]
I = [0 for i in range(N)]
for i in range(N-1):
  if S[i]=="A" and S[i+1]=="C":
    I[i+1]=I[i]+1
  else:
    I[i+1]=I[i]
      
for i in range(Q):
  l=LR[i][0]-1
  r=LR[i][1]-1
  print(I[r]-I[l])
### BUGGY CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
bc=[list(map(int,input().split())) for i in range(m)]
bc.sort(key=lambda x:x[1])
for b,c in bc[::-1]:
  a.extend([c]*b)
a.sort(reverse=True)
print(sum(a[:n]))

### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
bc=[list(map(int,input().split())) for i in range(m)]
bc.sort(key=lambda x:x[1])
for b,c in bc[::-1]:
  a.extend([c]*b)
  if len(a)>2*n:
    break
a.sort(reverse=True)
print(sum(a[:n]))
### BUGGY CODE ###

import sys
from operator import itemgetter


class BinaryIndexedTreeCustom:
    def __init__(self, n, init, func):
        self.size = n
        self.tree = [init] * (n + 1)
        self.depth = n.bit_length()
        self.init = init
        self.func = func

    def get(self, i):
        s = self.init
        while i > 0:
            s = self.func(s, self.tree[i])
            i -= i & -i
        return s

    def put(self, i, x):
        while i <= self.size:
            self.tree[i] = self.func(self.tree[i], x)
            i += i & -i


n, *aaa = map(int, sys.stdin.buffer.read().split())
bit1 = BinaryIndexedTreeCustom(n, 0, max)
bit2 = BinaryIndexedTreeCustom(n, n + 1, min)
aaa_with_index = list(enumerate(aaa, start=1))
aaa_with_index.sort(key=itemgetter(1))
ans = 0
for i, a in aaa_with_index:
    li = bit1.get(i)
    ri = bit2.get(n - i)
    ans += a * (i - li) * (ri - i)
    bit1.put(i, i)
    bit2.put(n + 1 - i, i)
print(ans)


### FIXED CODE ###

import sys
from operator import itemgetter


class BinaryIndexedTreeCustom:
    def __init__(self, n, init, func):
        self.size = n
        self.tree = [init] * (n + 1)
        self.depth = n.bit_length()
        self.init = init
        self.func = func

    def get(self, i):
        s = self.init
        while i > 0:
            s = self.func(s, self.tree[i])
            i -= i & -i
        return s

    def put(self, i, x):
        while i <= self.size:
            self.tree[i] = self.func(self.tree[i], x)
            i += i & -i


n, *aaa = map(int, sys.stdin.buffer.read().split())
bit1 = BinaryIndexedTreeCustom(n, 0, max)
bit2 = BinaryIndexedTreeCustom(n, n + 1, min)
aaa_with_index = list(enumerate(aaa, start=1))
aaa_with_index.sort(key=itemgetter(1))
ans = 0
for i, a in aaa_with_index:
    li = bit1.get(i)
    ri = bit2.get(n - i)
    ans += a * (i - li) * (ri - i)
    bit1.put(i, i)
    bit2.put(n + 1 - i, i)
print(ans)
### BUGGY CODE ###

# テスト対象（ABC081A - Placing Marbles (https://atcoder.jp/contests/abs/tasks/abc081_a)
H,W = map(int, input().split())
A = 0
dp = []
mat = []
for h in range(H):
    dpr = [-1] * W
    for w, x in zip(range(W), input()):
        if x == "#":
            dpr[w] = 0
            mat += [(h, w, 0)]
    dp += [dpr]

def search(dp, mat, conf, nH, nW, cnt):
    if not conf:
        return
    if dp[nH][nW] < 0:
        mat.insert(0, (nH, nW, cnt+1))
        dp[nH][nW] = cnt+1

i = 0
while len(mat) > 0:
    h, w, cnt = mat.pop()

    i+=1
    search(dp, mat, h > 0, h - 1, w, cnt)
    search(dp, mat, h < H-1, h + 1, w, cnt)
    search(dp, mat, w > 0, h , w - 1, cnt)
    search(dp, mat, w < W-1, h , w + 1, cnt)

import numpy as np
print(np.max(dp))


### FIXED CODE ###

from collections import deque
H,W = map(int, input().split())
A = 0
dp = [None] * H
mat = [None] * (H*W)
matS = matE = 0
for h in range(H):
    s = list(input())
    for w, x in zip(range(W), s):
        if x == "#":
            mat[matE] = (h, w, 0)
            matE+=1
    dp[h] = s

def search(dp, mat, nH, nW, cnt):
    global matE
    if dp[nH][nW] == ".":
        mat[matE] = (nH, nW, cnt+1)
        matE+=1
        dp[nH][nW] = "#"

while matS < matE:
    h, w, cnt = mat[matS]
    matS += 1

    if h > 0:
        search(dp, mat, h - 1, w, cnt)
    if h < H-1:
        search(dp, mat, h + 1, w, cnt)
    if w > 0:
        search(dp, mat, h , w - 1, cnt)
    if w < W-1:
        search(dp, mat, h , w + 1, cnt)

print(cnt)
### BUGGY CODE ###

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

for i in range(m//n,0,-1):
    if m%i==0 and m//i>=n:
        print(i)
        break


### FIXED CODE ###

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors
n,m=map(int,input().split())
ans=1
for i in make_divisors(m):
    if i>=n:
        ans=max(ans,m//i)
print(ans)
### BUGGY CODE ###

N = int(input())
data = [int(i) for i in input().split()]
sum = 1

for j in data:
    sum *= j
if sum > 10 ** 18:
    print(-1)
else:
    print(sum)
        


### FIXED CODE ###

import sys
N = int(input())
data = [int(i) for i in input().split()]
sum = 1

if 0 in data:
    print(0)
    sys.exit()

for j in data:
    sum *= j
    if sum > 10 ** 18:
        print(-1)
        sys.exit()
        
else:
    print(sum)
### BUGGY CODE ###

import numpy as np

size=input()
pro=input()

p=np.array(pro.split(" "),dtype=np.int32)

k_end=max(p)
k_start=min(p)

c=0
for k in range(k_start,k_end+1):
    a=len(p[k<=p])
    b=len(p[k>p])
    if(a==b):
        c+=1
    else:
        pass
print(c)

### FIXED CODE ###

import numpy as np

size=input()
pro=input()

p=np.array(pro.split(" "),dtype=np.int32)
p=np.sort(p)

me=int(len(p)/2)

print(p[me]-p[me-1])
### BUGGY CODE ###

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

A.sort()
F.sort(reverse=True)

def condition(num):
    count=0
    goal=[num//F[i] for i in range(N)]
    for i in range(0,N):
        if A[i]>goal[i]:
            count+=A[i]-goal[i]
    return K>=count

start=0
end=10**20
while end-start>1:
    test=(end+start)//2
    if condition(test):
        end=test
    else:
        start=test

if condition(start):
    print(start)
else:
    print(end)

### FIXED CODE ###

import sys

input=sys.stdin.readline

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

A.sort()
F.sort(reverse=True)

def condition(num):
    count=0
    goal=[num//F[i] for i in range(N)]
    for i in range(0,N):
        if A[i]>goal[i]:
            count+=A[i]-goal[i]
    return K>=count

start=0
end=2*(10**17)
while end-start>1:
    test=(end+start)//2
    if condition(test):
        end=test
    else:
        start=test

if condition(start):
    print(start)
else:
    print(end)
### BUGGY CODE ###

n,m=map(int,input().split())
x,y=[],[]
for i in range(m):
    a,b=map(int,input().split())
    if a==1:
        x.append(b)
    if b==n:
        y.append(a)

for i in x:
    if i in y:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")


### FIXED CODE ###

n,m=map(int,input().split())
x=[]
for i in range(m):
    a,b=map(int,input().split())
    if a==1:
        x.append(b)
    if b==n:
        x.append(a)
l=len(x)
if len(set(x))==l:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")
### BUGGY CODE ###

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

N, M = map(int,input().split())
to = [[] for _ in range(N)]
fr = [[] for _ in range(N)]
for _ in range(N-1+M):
    A, B = map(int,input().split())
    A -= 1
    B -= 1
    to[A].append(B)
    fr[B].append(A)

depth = [-1] * N

def dfs(v, d):
    depth[v] = max(depth[v], d)
    nd = d + 1
    for nv in to[v]:
        dfs(nv, nd)

root = -1
for v in range(N):
    if len(fr[v]) == 0:
        root = v
        break

dfs(root, 0)

vlist = [[] for _ in range(N)]
for v, d in enumerate(depth):
    vlist[d].append(v)

for v in range(N):
    d = depth[v]
    if d == 0:
        print(0)
        continue
    parent = set(vlist[d-1]) & set(fr[v])
    print(parent.pop()+1)


### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import deque

N, M = map(int,input().split())
to = [[] for _ in range(N)]
fr = [[] for _ in range(N)]
for _ in range(N-1+M):
    A, B = map(int,input().split())
    A -= 1; B -= 1
    to[A].append(B)
    fr[B].append(A)

# トポロジカルソート　計算量O(V+E)
# 有向グラフに用いる
# 閉路検出(DAGの判定)やDPの更新順序を明らかにするときなどに使える

# num[i] : iに入ってくる有効辺の本数
num = [0] * N

# グラフの構築でnumを更新しておく
num = [len(fr[v]) for v in range(N)]

S = deque()
L = []
#　例えば-1で初期化 dp = [-1] * N
'''  編集　'''

for v in range(N):
    if num[v] == 0:
        S.append(v)
        # 入次数0の頂点において例えば0で初期化　dp[v] = 0
        '''　編集　'''

while S:
    v = S.popleft()
    L.append(v)
    for nv in to[v]:
        num[nv] -= 1
        if num[nv] == 0:
            S.append(nv)
        # dpの更新　例えばmaxをとる dp[nv] = max(dp[nv], dp[v] + w[v])
        ''' 　編集 '''

# 閉路がある場合の処理
if len(L) != N:
    '''  編集　'''
    pass

index = [-1] * N
for i, v in enumerate(L):
    index[v] = i

for v in range(N):
    if v == L[0]:
        print(0)
        continue
    pv = -1
    d = N
    for cand in fr[v]:
        res = index[v] - index[cand]
        if res < d:
            d = res
            pv = cand
    pv += 1
    print(pv)
### BUGGY CODE ###

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

A.sort()
R = A[-2]

is_pairwise_coprime = True
is_setwise_coprime = True
checked = [0]*(R+1)
l = 0

for i in range(2, R+1):
    if checked[i]:
        continue
    
    # 調べる範囲を狭める
    while A[l] < i and l < N-1:
        l += 1
    if l == N-1:
        break
    
    # iで割り切れるAiの個数を数える
    tmp = 0
    for j in range(l, N):
        if A[j]%i == 0:
            tmp += 1
    # 2個以上あればnot pairwise coprime
    # N個あれば not setwise coprime
    if tmp > 1:
        is_pairwise_coprime = False
    if tmp == N:
        is_setwise_coprime = False
    
    if is_setwise_coprime == False:
        break
    
    # iの倍数はチェック済みにする
    n = i
    while n < R+1:
        checked[n] = 1
        n += i
    # print(checked, l)
if is_pairwise_coprime:
    print('pairwise coprime')
elif is_setwise_coprime:
    print('setwise coprime')
else:
    print('not coprime')

### FIXED CODE ###

from collections import defaultdict

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

Ones = A.count(1)
R = max(A)
nums = [0]*(R+1)

# 素因数テーブルの作成
D = [0]*(R+1)
for i in range(2, R+1):
    if D[i]:
        continue
    n = i
    while n < R+1:
        if D[n] == 0:
            D[n] = i
        n += i

# 素因子をカウント
for a in A:
    tmp = a
    while tmp > 1:
        prime_factor = D[tmp]
        nums[prime_factor] += 1
        while tmp%prime_factor == 0:
            tmp //= prime_factor
y = max(nums)
if y < 2:
    print('pairwise coprime')
elif y-Ones < N:
    print('setwise coprime')
else:
    print('not coprime')
### BUGGY CODE ###

num=int(input())
s=input()
count=0
for a in range(num-2):
  for b in range(a+1,num-1):
    for c in range(b+1,num):
      if (s[a]!=s[b] and s[b]!=s[c] and s[a]!=s[c]) and c-b!=b-a:
        count=count+1
print(count)


### FIXED CODE ###

num=int(input())
word=input()
alound=word.count("R")*word.count("G")*word.count("B")
for i in range(num-2):
  for j in range(i+1,num-1):
    k=2*j-i
    if k<=num-1:
      if word[i]!=word[j] and word[i]!=word[k] and word[k]!=word[j]:
        alound=alound-1
print(alound)