Harryxun/stf_run huggingface dataset:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

import sys
sys.setrecursionlimit(40000000)

n,q = mi()
b = [[] for i in range(n)]
ans = [0]*n
# O(n)
for i in range(n-1):
    a,c = mi()
    b[a-1].append(c-1)
    b[c-1].append(a-1)


def chil_pop(l):
    for i in b[l]:
        b[i].pop(b[i].index(l))
        chil_pop(i)

chil_pop(0)

def chil_add(z,x):
    ans[z] += x
    for i in b[z]:
        chil_add(i,x)

for i in range(q):
    p,x = mi()
    chil_add(p-1,x)

ans_str = ''
for i in range(n):
    # print(ans[i],end=' ')
    ans_str = ans_str + ans[i] + ' '
print(ans_str)


### FIXED CODE ###

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

import sys
sys.setrecursionlimit(40000000)

n,q = mi()
b = [[] for i in range(n)]
ans = [0]*n

# O(2n)
for i in range(n-1):
    a,c = mi()
    b[a-1].append(c-1)
    b[c-1].append(a-1)

# jun = []
# O(2n)
# def chil_pop(l,p):
#     jun.append(l)
#     for i in b[l]:
#         if i == p:
#             continue
#         chil_pop(i,l)
#     b[l] = p

# chil_pop(0,-1)


# O(q)
for i in range(q):
    p,x = mi()
    ans[p-1] += x


count = 0
q = [(0,-1)]
while q:
    c,p = q.pop()
    for i in b[c]:
        if i == p:
            continue
        ans[i] += ans[c]
        q.append((i,c))
    
    

# for i in jun[1:]:
#     ans[i] += ans[b[i]]

# ans_str = ''
# for i in range(n):
#     print(ans[i],end=' ')
#     # ans_str = ans_str + str(ans[i]) + ' '
print(*ans)
MOD = 10**9+7
N = int(input())

X = [[] for _ in range(N)]

for _ in range(N-1):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    X[y-1].append(x-1)
    
P = [-1] * N
def dfs(i):
    for j in X[i]:
        if j != 0 and P[j] < 0:
            P[j] = i
            dfs(j)

dfs(0)

for i in range(N):
    if i != 0:
        X[i].remove(P[i])

ans = 0
B = [0] * N
W = [0] * N

def dfs2(i):
    _ansb = 1
    _answ = 1
    for j in X[i]:
        __ansb, __answ = dfs2(j)
        _ansb *= __answ
        _answ *= (__ansb+__answ)
        _ansb %= MOD
        _answ %= MOD
    
    return (_ansb, _answ)

print(sum(dfs2(0)) % MOD)


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

MOD = 10**9+7
N = int(input())

X = [[] for _ in range(N)]

for _ in range(N-1):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    X[y-1].append(x-1)
    
P = [-1] * N
def dfs(i):
    for j in X[i]:
        if j != 0 and P[j] < 0:
            P[j] = i
            dfs(j)

dfs(0)

for i in range(N):
    if i != 0:
        X[i].remove(P[i])

ans = 0
B = [0] * N
W = [0] * N

def dfs2(i):
    _ansb = 1
    _answ = 1
    for j in X[i]:
        __ansb, __answ = dfs2(j)
        _ansb *= __answ
        _answ *= (__ansb+__answ)
        _ansb %= MOD
        _answ %= MOD
    
    return (_ansb, _answ)

print(sum(dfs2(0)) % MOD)
n = int(input)
ans = len(set([input() for _ in range(n)]))
print(ans)

### FIXED CODE ###

n = int(input())
ans = len(set([input() for _ in range(n)]))
print(ans)
N, M = [int(i) for i in input().split()]
A = {int(input()) for _ in range(M)}

dp = [0] * 20000
dp[0] = 1
dp[1] = 0 if 1 in A else 1
for i in range(N):
    if i+2 in A:
        continue
    dp[i+2] = dp[i] + dp[i+1]

print(dp[N] % 1000000007)

### FIXED CODE ###

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

dp = [0, 1]
for i in range(N):
    if i+1 in A: dp.append(0)
    else: dp.append(dp[i]+dp[i+1])
print(dp[N+1]%1000000007)
s=input().replace('\n', '')
t=input().replace('\n', '')
begin, end = len(s) - len(t), len(s)
ans=''
while begin>=0:
    origin = s[begin:end]
    print(origin)
    flag=1
    for i in range(len(t)):
        if origin[i]!=t[i] and origin[i]!='?':
            flag=0
            break
    if flag:
        ans = s[:begin]+t+s[end:]
    begin-=1
    end-=1
print("UNRESTORABLE" if flag else ans.replace('?', 'a'))


### FIXED CODE ###

s=input().replace('\n', '')
t=input().replace('\n', '')
begin, end = len(s) - len(t), len(s)
ans=''
while begin>=0:
    origin = s[begin:end]
    flag=1
    
    for i in range(len(t)):
        if origin[i]!=t[i] and origin[i]!='?':
            flag=0
            break
    if flag:
        ans = s[:begin]+t+s[end:]
        break
    begin-=1
    end-=1
print("UNRESTORABLE" if not len(ans) else ans.replace('?', 'a'))
# coding: utf-8
# Your code here!

food = [int(input()) for i in range(5)]

minr = 10
minf = 0
for f in food:
    if f % 10 != 0 :
        if f % 10 < minr :
            minr = f % 10
            minf = f

food.remove(minf)
food.append(minf)

sumf = 0
i = 0
for f in food:
    if i == 4:
        sumf += f
    elif f % 10 != 0:
        sumf += int(f/10) * 10 + 10
    else:
        sumf += f
    i+=1
print(sumf)

### FIXED CODE ###

# coding: utf-8
# Your code here!

food = [int(input()) for i in range(5)]

minr = 10
minf = 0
for f in food:
    if f % 10 != 0 :
        if f % 10 < minr :
            minr = f % 10
            minf = f
if minf == 0:
    minf = food[0]
        

food.remove(minf)
food.append(minf)

sumf = 0
i = 0
for f in food:
    if i == 4:
        sumf += f
    elif f % 10 != 0:
        sumf += int(f/10) * 10 + 10
    else:
        sumf += f
    i+=1
print(sumf)
n,m = map(int, input().split())

M = m
lst, count = [],[]
for i in range(2,int(math.sqrt(m))+1):
    while M % i == 0:
        M = M // i
        if i not in lst:
            count.append(1)
            lst.append(i)
        else:
            count[-1] += 1
if M > 1:
    lst.append(M)
    count.append(1)       

ans = 1
for i in count:
    ans *= scipy.special.comb(i+n-1,i)
    ans = ans % (10**9+7) 

print(int(ans))

### FIXED CODE ###

import scipy.misc
import math

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

M = m
lst, count = [],[]
if M == 1:
    print(1)
else:
    for i in range(2,int(math.sqrt(m))+1):
        while M % i == 0:
            M = M // i
            if i not in lst:
                count.append(1)
                lst.append(i)
            else:
                count[-1] += 1
    if M > 1:
        lst.append(M)
        count.append(1)       

    ans = 1
    for i in count:
        ans = ans * scipy.misc.comb(i+n-1,i, exact=1)
        ans = ans % (10**9+7) 

    print(int(ans))
#%%
import copy 

H, W = map(int, input().split())
c = [[int(_) for _ in input().split()] for _ in range(10)]
A = [[int(_) for _ in input().split()] for _ in range(H)]

d = copy.deepcopy(c)

for i in range(10):
    for j in range(10):
        for k in range(10):
            d[i][j] = min(d[i][j], d[i][k]+d[k][j])


ans = 0
#for i in range(H):
#    for j in range(W):
#        if A[i][j] == 0 or A[i][j] >= 2:
#            ans += d[A[i][j]][1]


for i in a:
    for j in i:
        if j > 1 or j == 0:
            ans += d[j][1]

print(ans)

### FIXED CODE ###

#%%
import copy 

H, W = map(int, input().split())
c = [[int(_) for _ in input().split()] for _ in range(10)]
A = [[int(_) for _ in input().split()] for _ in range(H)]

d = copy.deepcopy(c)

for k in range(10):
    for i in range(10):
        for j in range(10):
            d[i][j] = min(d[i][j], d[i][k]+d[k][j])


ans = 0
for i in range(H):
    for j in range(W):
        if A[i][j] == 0 or A[i][j] >= 2:
            ans += d[A[i][j]][1]


print(ans)
# coding: utf-8

import math

N = int(raw_input())

h = int(math.ceil(N/4.0))
n = int(math.ceil(h*4*N/4.0/(h*4-N)))
w = 11451419198101145141919810
print h, n, w

### FIXED CODE ###

def solver():
    N = int(raw_input())

    for h in xrange(1, 3501):
        for n in xrange(1, 3501):
            x = N * h * n;
            y = 4 * n * h - N * n - N * h;
            if y > 0 and x % y == 0:
                w = x / y
                return map(str, [h, n, w])


print " ".join(solver())
x = int(input())
for a in range(1,100):
    a_5 = a**5
    
    if a_5 > x:
        b = 1
        s = 0
        while s > x:
            s = a_5 - b**5
            if s == x:
                print(a, b)
                sys.exit()
            b += 1
            
    elif a_5 < x:
        b = -1
        s = 0
        while s < x:
            s = a_5 - b**5
            if s == x:
                print(a, b)
                sys.exit()
            b -= 1
    else:
        print(a,0)
        sys.exit()


### FIXED CODE ###

import sys

x = int(input())
for a in range(1,1000):
    a_5 = a**5
    if a_5 > x:
        b = 1
        s = x+1
        while s > x:
            s = a_5 - b**5
            if s == x:
                print(a, b)
                sys.exit()
            b += 1
            
    elif a_5 < x:
        b = -1
        s = x-1
        while s < x:
            s = a_5 - b**5
            if s == x:
                print(a, b)
                sys.exit()
            b -= 1
    else:
        print(a,0)
        sys.exit()
N, M = map(int, input().splilt())
p = list(map(int, input().splilt()))
print(sum(sorted(p)[:M]))

### FIXED CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))
print(sum(sorted(p)[:K]))
a, b = map(int, input().split())
if b%a == 0:
    print(A+B)
else:
    print(B-A)

### FIXED CODE ###

A, B = map(int, input().split())
if B%A == 0:
    print(A+B)
else:
    print(B-A)
from collections import defaultdict
import copy
s = input()
import sys
n_s = len(s)
t = input()
n_t = len(t)

alphabet = [chr(i) for i in range(97, 97+26)]
al_d = {}
for i in range(26):
    al_d[alphabet[i]] = i

chr_firstind = defaultdict(lambda:-1)
chr_nextind = defaultdict(lambda:-1)
i_to_chr_nextind = [0] * n_s
for i in range(n_s-1,-1,-1):
    chr_firstind[s[i]] = i
    i_to_chr_nextind[i] = copy.copy(chr_nextind)
    chr_nextind[s[i]] = i 

first_target = t[0]
previous_ind = chr_firstind[first_target]
if n_t == 1:
    if previous_ind == -1:
        print(-1)
    else:
        print(first_ind)+1
    sys.exit()
s_used = 0
for i in range(1,n_t):
    # 一つ前のtarget_indを使って、次のtargetのs内でのindexを求める
    d = i_to_chr_nextind[previous_ind]
    next_ind = d[t[i]]
    if next_ind == -1:
        s_used += 1
        next_ind = chr_firstind[t[i]]
        if next_ind == -1:
            print(-1)
            sys.exit()
    previous_ind = next_ind
print(n_s*s_used+previous_ind+1)




### FIXED CODE ###

from collections import defaultdict
import copy
import sys
s = input()
n_s = len(s)
t = input()
n_t = len(t)

chr_firstind = defaultdict(lambda:-1)
chr_nextind = defaultdict(lambda:-1)
i_to_chr_nextind = [0] * n_s
for i in range(n_s-1,-1,-1):
    chr_firstind[s[i]] = i
    i_to_chr_nextind[i] = copy.copy(chr_nextind)
    chr_nextind[s[i]] = i 

first_target = t[0]
previous_ind = chr_firstind[first_target]
if previous_ind == -1:
    print(-1)
    sys.exit()
if n_t == 1:
    print(previous_ind+1)
    sys.exit()
s_used = 0
for i in range(1,n_t):
    # 一つ前のtarget_indを使って、次のtargetのs内でのindexを求める
    d = i_to_chr_nextind[previous_ind]
    next_ind = d[t[i]]
    if next_ind == -1:
        s_used += 1
        next_ind = chr_firstind[t[i]]
        if next_ind == -1:
            print(-1)
            sys.exit()
    previous_ind = next_ind
print(n_s*s_used+previous_ind+1)
print("YES"*(int(input()[::2])%4<1)or"NO")


### FIXED CODE ###

print "YES"*(int(raw_input().replace(" ", ""))%4==0)or"NO"
while True:
    (x, y) = [int(i) for i in sys.stdin.readline().split(' ')]
    if x == 0 and y == 0
        break     
    if x > y:
        z = x
        x = y
        y = z     
    print(x, y)

### FIXED CODE ###

import sys     
while True:
    (x, y) = [int(i) for i in sys.stdin.readline().split(' ')]     
    if x == 0 and y == 0:
        break     
    if x > y:
        z = x
        x = y
        y = z     
    print(x, y)
#!/usr/bin/env python
#coding: UTF-8
import sys
import math

line = []
for l in sys.stdin:
    for i in l.split(' '):
    	line.append(float(i))
a = math.sqrt((line[0]-line[2])**2+(line[1]-line[3])**2)
print '%.12f'%a

### FIXED CODE ###

import math

x1,y1,x2,y2 = map(float,raw_input().split())
a = math.sqrt((x1-x2)**2+(y1-y2)**2)
print '%f'%a
import sys
def input():
    return sys.stdin.readline()[:-1]

n,m=map(int,input().split())
#xyz = [[]for i in range(m)]
g = [[]for i in range(n)]
for i in range(m):
    x,y,z = map(int,input().split())
    g[x-1].append(y-1)
    g[y-1].append(x-1)

seen = [0 for i in range(n)]

def dfs(i):
    for nec in g[i]:
        if seen[nec]!=0:continue
        seen[nec]=1
        dfs(nec)

cnt = 0
for i in range(n):
    if seen[i] == 0:
        seen[i] = 1
        dfs(i)
        cnt+=1

print(cnt)


### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(1000000)
n,m=map(int,input().split())
#xyz = [[]for i in range(m)]
g = [[]for i in range(n)]
for i in range(m):
    x,y,z = map(int,input().split())
    g[x-1].append(y-1)
    g[y-1].append(x-1)

seen = [0 for i in range(n)]

def dfs(i):
    for nec in g[i]:
        if seen[nec]!=0:continue
        seen[nec]=1
        dfs(nec)

cnt = 0
for i in range(n):
    if seen[i] == 0:
        seen[i] = 1
        dfs(i)
        cnt+=1

print(cnt)
def decice_winner(a, b):
    if a > b and b != 0:
        return b
    else:
        return a
def calc_min(a, b):
    while True:
        if a <= 1 or b <=1:
            return decice_winner(a, b)
        elif a > b and a / b > 0 :
            a = a % b
        elif b > a and b / a > 0:
            b = b % a
        else:
            return decice_winner(a, b)

def main():
    _ = input()
    monsters = list(set([int(n) for n in input().split(" ")]))
    min1 = min(monsters)
    monsters.remove(min1)
    monsters = list(set([n % min1 for n in monsters]))
    monsters.remove(0)
    if len(monsters) == 0:
        print(min1)
    else:
        min2 = min(monsters)
        print(calc_min(min1, min2))

if __name__ == "__main__":
    main()

### FIXED CODE ###

from functools import reduce

def gcd(a, b):
    x = max(a, b)
    y = min(a, b)
    if x % y == 0:
        return y
    else:
        while x % y != 0:
            z = x % y
            x = y 
            y = z
        else:
            return z

def main():
    _ = input()
    monsters = [int(n) for n in input().split(" ")]
    max_gcd = reduce(gcd, monsters)
    print(max_gcd)

if __name__ == "__main__":
    main()
A=list(map(int, input().split()))
n=len(A)
A.sort()
for i in range(N-1):
  if A[i]==A[i+1]:
    print('NO')
    exit()
else:
  print('YES')

### FIXED CODE ###

N=int(input())
A=list(map(int, input().split()))
A.sort()
if N==1:
  print('YES')
  exit()
for i in range(N-1):
  if A[i]==A[i+1]:
    print('NO')
    exit()
else:
  print('YES')
K = int(input())
A = list(map(int,input().split()))

if A[-1] != 2:
	print(-1)
	exit(0)

minval = 2
maxval = 3
for i in range(K-1,-1,-1):
	if maxval < A[i] or (minval > A[i] and ((maxval - (maxval % A[i]) < minval)):
		print(-1)
		exit(0)

	if minval > A[i]:
		if minval % A[i] != 0:
			minval = minval + (A[i] - (minval % A[i]))

		maxval = (maxval - (maxval % A[i]) + A[i] - 1)

	else:
		maxval = A[i] + (A[i] - 1)
		minval = A[i]
		

print(str(minval) + " " + str(maxval))


### FIXED CODE ###

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

if A[-1] != 2:
	print(-1)
	exit(0)

minval = 2
maxval = 3
for i in range(K-1,-1,-1):
	if maxval < A[i] or (minval > A[i] and ((maxval - (maxval % A[i]) < minval))):
		print(-1)
		exit(0)

	if minval > A[i]:
		if minval % A[i] != 0:
			minval = minval + (A[i] - (minval % A[i]))

		maxval = (maxval - (maxval % A[i]) + A[i] - 1)

	else:
		maxval = A[i] + (A[i] - 1)
		minval = A[i]
		

print(str(minval) + " " + str(maxval))
x, a = int(input().split())

print(10 if x < a else 0)

### FIXED CODE ###

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

print(0 if x < a else 10)
class UnionFind:
    def __init__(self, num):
        self.p = [x for x in range(num)]
    def root(self, x):
        if self.p[x] == x:
            return x
        self.p[x] = self.root(self.p[x])
        return self.p[x]
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx is ry:
            return
        self.p[rx] = ry

def main():
    N, M = (int(x) for x in input().split())
    u = UnionFind(N)

    for i in range(M):
        x,y,_ = map(int, input().split())
        u.unite(x-1, y-1)

    rlist = set([])
    for i in range(N):
        parent = u.root(i)
        rlist.add(parent)

    print(len(rlist))

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

class UnionFind:
    def __init__(self, num):
        self.p = [x for x in range(num)]
    def root(self, x):
        if self.p[x] == x:
            return x
        else:
            self.p[x] = self.root(self.p[x])
            return self.p[x]
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx != ry:
            self.p[ry] = rx

def main():
    N, M = (int(x) for x in input().split())
    u = UnionFind(N)

    for i in range(M):
        x,y,_ = map(int, input().split())
        u.unite(x-1, y-1)

    rlist = set()
    for i in range(N):
        rlist.add(u.root(i))

    print(len(rlist))

if __name__ == '__main__':
    main()
N, A, B = list(map(int, input().split()))

blue_num = A * (N // (A + B)) + (N % (A + B) % A)
print(blue_num)

### FIXED CODE ###

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

try:
    blue_num = A * (N // (A + B))
    residue = N - ((A + B) * (N // (A + B)))
    if(residue > A):
        blue_num += A
    else:
        blue_num += residue
except ZeroDivisionError:
    blue_num = 0

print(blue_num)
N = int(input())
array = []
for _ in range(N):
  array.append(int(input()))
AC = 0
WA = 0
TLE = 0
RE = 0
for test in array:
  if 'AC' == test:
    AC += 1
  elif 'WA' == test:
    WA += 1
  elif 'TLE' == test:
    TLE += 1
  elif 'RE' == test:
    RE += 1
print(f'AC x {AC}')
print(f'WA x {WA}')
print(f'TLE x {TLE}')
print(f'RE x {RE}')

### FIXED CODE ###

N = int(input())
array = []
for _ in range(N):
  array.append(input())
AC = 0
WA = 0
TLE = 0
RE = 0
for test in array:
  if 'AC' == test:
    AC += 1
  elif 'WA' == test:
    WA += 1
  elif 'TLE' == test:
    TLE += 1
  elif 'RE' == test:
    RE += 1
print(f'AC x {AC}')
print(f'WA x {WA}')
print(f'TLE x {TLE}')
print(f'RE x {RE}')
import heapq

N,M = map(int,input().split())
value = list(map(int,input().split()))
value = list(map(lambda x: x*(-1), value))
value = heapq.heapify(value)

for i in range(M):
  num = (heapq.heappop(value)*(-1)//2)*(-1)
  heapq.heappush(value,num)

print(sum(list(map(lambda x: x*(-1), value))))


### FIXED CODE ###

import heapq as hp
n, m = map(int, input().split())
list_A = list(map(int, input().split()))
 
a_q = []
for i in list_A:
    hp.heappush(a_q, -1*i)
    
for i in range(m):
    tmp = hp.heappop(a_q)
    tmp = hp.heappush(a_q, int(tmp/2))
    
print(-sum(a_q))
5 3
5
7
5
7
7

### FIXED CODE ###

N,K=map(int,input().split(' '))
h=sorted([int(input()) for i in range(N)])
ans = 10**9
for i in range(N-K+1):
    ans = min(ans,h[i+K-1]-h[i])
print(ans)
n, y = map(int, input().split())
k = 0
result = 0

for i in range(n + 1):
    for j in range(n + 1):
        k = n - i - j
        ans = 10000 * i + 5000 * j + 1000 * k
        if (ans == y):
            print(a, b, c)
            result += 1
            exit()
            
if result == 0:
    print('-1 -1 -1')


### FIXED CODE ###

n, y = map(int, input().split())
result = 0

for i in range(n+1):
    for j in range(n+1):
        k = n - i - j
        z = 10000*i + 5000*j + 1000*k
        if z == y and k >= 0:
            result += 1
            print(i, j, k)
            exit()

if result == 0:
    print('-1 -1 -1')
while 1:
   H, W = map(raw_input().split())

   if H == 0 and W == 0:
      break
   else:
      for i in range(0, H-1):
         for j in range(0, W-1):
            print #
         print '\n'
   print '\n'

### FIXED CODE ###

while 1:
   H, W = map(int, raw_input().split())

   if H == 0 and W == 0: 
      break
   for i in range(H):
      print "#"*W
   print ""
import sys
import heapq
input = sys.stdin.readline

class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

n = int(input())
uf = UnionFind(n)
d = {}

for i in range(n):
    x, y = map(int, input().split())
    d[x] = (i, y)
    
q = []
heapq.heapify(q)

for x in range(n):
    i, y = d[x]
    while q[0][0] < y:
        y2, i2 = heapq.heappop(q)
        uf.union(i,i2)
    heapq.heappush(q, (y,i))

for i in range(n):
    p = uf.find(i)
    print(-uf.parents[p])


### FIXED CODE ###

import sys
import heapq
input = sys.stdin.readline

class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

n = int(input())
uf = UnionFind(n)
d = {}

for i in range(n):
    x, y = map(int, input().split())
    d[x] = (i, y)
    
q = []
heapq.heapify(q)

for x in range(n):
    i, y = d[x+1]
    ym, im = 0, 0
    while q and q[0][0] < y:
        y2, i2 = heapq.heappop(q)
        if ym == 0:
            ym = y2
            im = i2
        uf.union(i,i2)
    heapq.heappush(q, (y,i))
    if ym:
        heapq.heappush(q, (ym,im))

for i in range(n):
    p = uf.find(i)
    print(-uf.parents[p])