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

from pprint import pprint
from collections import deque, defaultdict

n, q = list(map(int, input().strip().split(" ")))
edges = defaultdict(set)
for _ in range(n-1):
    a_i, b_i = list(map(int, input().strip().split(" ")))
    # edges[a_i-1].append(b_i-1)
    # edges[b_i-1].append(a_i-1)
    edges[a_i-1].add(b_i-1)
    edges[b_i-1].add(a_i-1)

# p = defaultdict(int)
# counter = defaultdict(int)
counter = [0] * n
p = [0] * n
x = []
for _ in range(q):
    p_i, x_i = list(map(int, input().strip().split(" ")))
    # p[p_i-1] += x_i
    counter[p_i-1] += x_i


parents = deque()
# parents.append(0)
# parents = []
parents.append(0)
visited = set()
while parents:
    parent = parents.popleft()
    # parent = parents.pop()
    if parent in visited:
        continue
    visited.add(parent)
    # counter[parent] += p[parent]
    # print("parent")
    # print(parent, counter[parent])
    for child in edges[parent]:
        if child in visited:
            continue
        # if counter[child] != 0:
        #    continue
        counter[child] += counter[parent]
        # print("child")
        # print(child, counter[child])
        parents.append(child)
        # parents.add(child)

#print(" ".join(list(map(str, counter.values()))))
print(" ".join(list(map(str, counter))))

### FIXED CODE ###

from collections import deque


def solve(n, q, a, b, p, x):
    counter = [0] * n
    q_sum = [0] * n
    for i in range(q):
        q_sum[p[i]] += x[i]
    # pprint(q_sum)

    edges = {}
    for i in range(n-1):
        if a[i] not in edges:
            edges[a[i]] = []
        edges[a[i]].append(b[i])
    # pprint(edges)

    counter[0] = q_sum[0]
    children = deque()
    for child in edges[0]:
        counter[child] = q_sum[0]
        children.append(child)
    while children:
        child = children.popleft()
        counter[child] += q_sum[child]
        # print("child")
        # print(child, counter[child])
        if child in edges:
            for c in edges[child]:
                counter[c] = counter[child]
                # print("c")
                # print(c, counter[c])
                children.append(c)

    print(" ".join(list(map(str, counter))))

if __name__ == "__main__":
    n, q = list(map(int, input().strip().split(" ")))
    a = []
    b = []
    for _ in range(n-1):
        a_i, b_i = list(map(int, input().strip().split(" ")))
        a.append(a_i - 1)
        b.append(b_i - 1)

    p = []
    x = []
    for _ in range(q):
        p_i, x_i = list(map(int, input().strip().split(" ")))
        p.append(p_i-1)
        x.append(x_i)
    solve(n, q, a, b, p, x)
### BUGGY CODE ###

import math
import copy
import numpy as np

N = int(input())
As = input().split()
A = [0 for i in range(N)]
for i in range(N):
  A[i] = int(As[i])

# relabel A's elements
A_unique = list(set(A))
to_unique = {}
for i,a in enumerate(A_unique):
  to_unique[a] = i
for i in range(N):
  A[i] = to_unique[A[i]]

# count number of each label appearing
counts = np.zeros(len(A_unique))
for _,A_i in enumerate(A):
  counts[A_i] += 1

for k in range(N):
  counts[A[k]] -= 1 # herasu
  print(int(np.sum(counts*(counts-1)/2)))
  counts[A[k]] += 1 # modosu


### FIXED CODE ###

import math
import copy
import numpy as np

N = int(input())
As = input().split()
A = [0 for i in range(N)]
for i in range(N):
  A[i] = int(As[i])

# relabel A's elements
A_unique = list(set(A))
num_unique = len(A_unique)
to_unique = {}
for i,a in enumerate(A_unique):
  to_unique[a] = i
for i in range(N):
  A[i] = to_unique[A[i]]

# count number of each label appearing
counts = [0 for i in range(num_unique)]
for _,A_i in enumerate(A):
  counts[A_i] += 1
answer_total = 0
for count in counts:
  answer_total += int(count*(count-1)/2)

spoiler = [-1 for i in range(num_unique)]
for k in range(N):
  if spoiler[A[k]]<0:
    answer_k = answer_total - (counts[A[k]]-1)
    spoiler[A[k]] = answer_k
  else:
    answer_k = spoiler[A[k]]
  print(answer_k)
### BUGGY CODE ###

def calculate_PD(exponent):

    D_count = exponent.count("D")
    PD_count = exponent.count("PD")

    return D_count + PD_count



T = input()

hatena_count = T.count("?")

patternes = []
for i in range(2**hatena_count):
    binary = format(i, 'b').zfill(hatena_count)

    pattern = binary.replace("0", "P").replace("1", "D")

    patternes.append(pattern)


exponent_list = []
for pattern in patternes:
    exponent = T[:]

    for i in range(hatena_count):
        exponent = exponent.replace("?", pattern[i], 1)

    exponent_list.append(exponent)


max_PD = 0
max_exponent = ""
for exponent in exponent_list:
    PD = calculate_PD(exponent)

    if PD > max_PD:
        max_PD = PD
        max_exponent = exponent

print(max_exponent)

### FIXED CODE ###

T = input()
hatena_count = T.count("?")

pattern = ""
for i in range(hatena_count):
    pattern += "D"

max_exponent = T
for i in range(hatena_count):
    max_exponent = max_exponent.replace("?", pattern[i], 1)

print(max_exponent)
### BUGGY CODE ###

n = int(input())
P = list(map(int, (input().split())))
count = 1
for i in range (1, n):
    if P[i] <= min(P[:i]):
        count += 1

print(count)

### FIXED CODE ###

n = int(input())
P = list(map(int, (input().split())))
count = 1
tmp = P[0]
for i in range (1, n):
    if P[i] <= tmp:
        count += 1
        tmp = P[i]
print(count)
### BUGGY CODE ###

import collections

h, w, n = map(int, input().split())
pos = collections.defaultdict(lambda: collections.defaultdict(bool))
squares = collections.defaultdict(lambda: collections.defaultdict(bool))
for index in range(n):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    pos[a][b] = True
    for i in range(-2, 1):
        for j in range(-2, 1):
            y = a + i
            x = b + j
            if 0 <= x < w - 2 and 0 <= y < h - 2:
                squares[y][x] = True
counter = collections.Counter()
for y, xs in squares.items():
    for x in xs:
        count = 0
        for i in range(3):
            for j in range(3):
                if pos[y + i][x + j]:
                    count += 1
        counter[count] += 1
print((h - 2) * (w - 2) - sum(counter.values()))
for i in range(1, 10):
    print(counter[i])

### FIXED CODE ###

import collections

h, w, n = map(int, input().split())
squares = collections.defaultdict(lambda: collections.defaultdict(int))
for index in range(n):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    for i in range(-2, 1):
        for j in range(-2, 1):
            y = a + i
            x = b + j
            if 0 <= x < w - 2 and 0 <= y < h - 2:
                squares[y][x] += 1
counter = collections.Counter()
for y, xs in squares.items():
    for x, count in xs.items():
        counter[count] += 1
print((h - 2) * (w - 2) - sum(counter.values()))
for i in range(1, 10):
    print(counter[i])
### BUGGY CODE ###

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

R = [None] * S.count("R")
G = [None] * S.count("G")
B = [None] * S.count("B")

ri = 0
gi = 0
bi = 0
for i in range(N):
    if S[i] == "R":
        R[ri] = i+1
        ri+=1
    elif S[i] == "G":
        G[gi] = i+1
        gi += 1
    else:
        B[bi] = i+1
        bi += 1

c = 0
for r in R:
    for g in G:
        for d in [(r + g) / 2, 2 * r - g, 2 * g - r]:
            if d in B:
                c += 1

ans = len(R) * len(G) * len(B) - c
print(ans)


### FIXED CODE ###

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

R = [None] * S.count("R")
G = [None] * S.count("G")
B = [None] * S.count("B")

ri = 0
gi = 0
bi = 0
for i in range(N):
    if S[i] == "R":
        R[ri] = i+1
        ri+=1
    elif S[i] == "G":
        G[gi] = i+1
        gi += 1
    else:
        B[bi] = i+1
        bi += 1
R = set(R)
G = set(G)
B = set(B)

c = 0
for r in R:
    for g in G:
        for d in [(r + g) / 2, 2 * r - g, 2 * g - r]:
            if d in B:
                c += 1

ans = len(R) * len(G) * len(B) - c
print(ans)
### BUGGY CODE ###

S = str(input())
ans = 0

if len(S) <= 3:
    print(0)
else:   
    for i in range(len(S)):
        for j in range(i+1,len(S)+1):
            if int(S[i:j]) % 2019 == 0:
                ans += 1
    print(ans)

### FIXED CODE ###

S = input()[::-1]

cnts = [0]*2019
cnts[0] = 1
num = 0
d = 1
ans = 0

for i in S:
    num += int(i) * d
    d *= 10
    num %= 2019
    d %= 2019
    cnts[num] += 1

for j in cnts:
    ans += j * (j-1) // 2 

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

import sys
from collections import deque, Counter, defaultdict
from fractions import gcd
input = sys.stdin.readline

def eprint(s):
    if type(s) != type('str'):
        s=str(s)

    sys.stderr.write(s+'\n')
    return

def expected_value(n):
    ans = 0

    for i in range(1, n+1):
        ans += i/n

    # eprint(ans)
    return ans

def main():
    n, k = map(int, input().split())
    Ps = list(map(int, input().split()))
    
    Cs = [0]*n
    for i in range(n):
        if i == 0:
            Cs[i] = Ps[i]
        else:
            Cs[i] = Cs[i-1] + Ps[i]
    
    Ds = list()
    mi = -10**9
    mix = 0
    for i in range(n-k+1):
        if i == 0:
            Ds.append(Cs[i+k-1])
        else:
            Ds.append(Cs[i+k-1] - Cs[i-1])

        if Ds[i] > mi:
            mi = Ds[i]
            mix = i

    
    #mix ~ mix+kまでの
    v = int()
    for i in range(k):
        v += expected_value(Ps[mix+i])
        
    print(v)

    return

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from collections import deque, Counter, defaultdict
from fractions import gcd
input = sys.stdin.readline

def eprint(s):
    if type(s) != type('str'):
        s=str(s)

    sys.stderr.write(s+'\n')
    return

def expected_value(n):
    ans = 0

    for i in range(1, n+1):
        ans += i/n

    # eprint(ans)
    return ans

def main():
    n, k = map(int, input().split())
    Ps = list(map(int, input().split()))
    
    Cs = [0]*n
    for i in range(n):
        if i == 0:
            Cs[i] = Ps[i]
        else:
            Cs[i] = Cs[i-1] + Ps[i]
    
    Ds = list()
    mi = -10**9
    mix = 0
    for i in range(n-k+1):
        if i == 0:
            Ds.append(Cs[i+k-1])
        else:
            Ds.append(Cs[i+k-1] - Cs[i-1])

        if Ds[i] > mi:
            mi = Ds[i]
            mix = i

    
    #mix ~ mix+kまでの
    v = int()
    for i in range(k):
        v += expected_value(Ps[mix+i])
        
    print(v)

    return

if __name__ == '__main__':
    main()
### BUGGY CODE ###

S = input()
be = len(S)

while True:
    tmp_S = S
    S = S.replace('01','').replace('10','').replace('01','').replace('10','')
    if tmp_S==S:
        break
af = len(S)
print(be-af)

### FIXED CODE ###

s = input()

one = s.count('1')
zero = s.count('0')

print(2*min(one,zero))
### BUGGY CODE ###

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

for i in range(q):
    cnt = 0
    start = int(lr[i][0])-1
    end = int(lr[i][1])-1

    for j in range(start, end):
        if s[j] == 'A' and s[j+1] == 'C':
                cnt += 1

    print(cnt)


### FIXED CODE ###

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

n = len(s)
ary = [0 for i in range(len(s)+1)]

for i in range(1, n):
    if s[i-1] == 'A' and s[i] == 'C':
        ary[i+1] = ary[i] + 1
    else:
        ary[i+1] = ary[i]

for i in range(q):
    ans = ary[int(lr[i][1])] - ary[int(lr[i][0])]
    print(ans)
### BUGGY CODE ###

import collections

N = int(input())
ans = [collections.Counter(list(input())) for _ in range(N)]
count = 0
for i in range(N):
    for j in range(i+1,N):
        if ans[i] == ans[j]:
            count += 1

print(count)


### FIXED CODE ###

N = int(input())
words = {}

ans = 0
for _ in range(N):
    w = list(input())
    w.sort()
    w = "".join(w)
    if w not in words:
        words[w] = 1
    else:
        ans += words[w]
        words[w] += 1
print(ans)
### BUGGY CODE ###

n = int(input())
P = [int(el) for el in input().split(" ")]

ans = 0
for i in range(n):
	for j in range(i):
		if P[i] <= P[j]:
			pass
		else:
			break
	else:
		ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
P = [int(el) for el in input().split(" ")]

ans = 1
m = P[0]
for i in range(1, n):
	if P[i] <= m:
		ans += 1
	m = min(m, P[i])

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

N, K = map(int,input().split())
dices = list(map(int,input().split()))
list =[]
for i in range(N-K+1):
    check = 0
    for j in range(K):
        check += dices[i+j]
    list.append(check)
print((max(list)+K)/2)

### FIXED CODE ###

N, K = map(int,input().split())
dices = list(map(int,input().split()))
list =[]
check=0
for i in range(K):
    check+=dices[i]
list.append(check)
for j in range(N-K):
    check -= dices[j]
    check += dices[j+K]
    list.append(check)    
print((max(list)+K)/2)
### BUGGY CODE ###

from copy import deepcopy

n = int(input())
S_origin = [int(_) for _ in input().split()]
q = int(input())
T = [int(_) for _ in input().split()]

cnt = 0
for t in T:

    S = deepcopy(S_origin)
    while S:
        ind = len(S) // 2

        if t == S[ind]:
            cnt += 1
            break
        elif t < S[ind]:
            S = S[:ind]
        else:
            S = S[ind + 1:]

print(cnt)



### FIXED CODE ###

# def binary_search_original(ary, target):

#     if ary:
#         ind = len(ary) // 2
#         if target == ary[ind]:
#             return True
#         elif target < ary[ind]:
#             return binary_search(ary[:ind], target)
#         else:
#             return binary_search(ary[ind + 1:], target)

#     else:
#         return False


def binary_search(ary, target):

    left = 0
    right = len(ary)

    while left < right:
        mid = (left + right) // 2

        if ary[mid] == target:
            return True
        elif ary[mid] < target:
            left = mid + 1
        else:
            right = mid

    return False


if __name__ == '__main__':

    n = int(input())
    S = [int(_) for _ in input().split()]
    q = int(input())
    T = [int(_) for _ in input().split()]
    cnt = 0

    for target in T:
        if binary_search(S, target):
            cnt += 1

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

from collections import deque

def main():
  n, m = map(int, input().split())
  tree_to = [[] for _ in range(n)]
  tree_from = [[] for _ in range(n)]
  for i in range(m):
    x, y = map(int, input().split())
    tree_to[x-1].append(y-1)
    tree_from[y-1].append(x-1)
  
  ans = [0]*n
  already = [False]*n
  for i in range(n):
    if already[i]:
      continue
    already[i] = True
    not_yet = deque(tree_to[i])
    while not_yet:
      key = not_yet.pop()
      if ans[key] or not tree_to[key]:
        already[key] = True
        search = deque(tree_from[key])
        while search:
          already[i]
          sub = search.popleft()
          ans[sub] = 1
          for v in tree_to[sub]:
            if ans[sub] < ans[v]+1:
              ans[sub] = ans[v]+1
          for v in tree_from[sub]:
            search.append(v)
        continue
      for v in tree_to[key]:
        not_yet.append(v)
  print(max(ans))
      

if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100007)

def main():
    n, m = map(int, input().split())
    
    grid = [[] for _ in range(n)]
    
    for _ in range(m):
        x, y = map(int, input().split())
        grid[x-1].append(y-1)
    
    memo = [-1]*n
    
    def dp(n):
        if memo[n] != -1:
            return memo[n]
        res = 0
        for v in grid[n]:
            res = max(res, dp(v)+1)
        memo[n] = res
        return res
    
    ans = 0
    for i in range(n):
        sub = dp(i)
        if ans < sub:
            ans = sub
        
    print(ans)
    
    
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

# -*- coding:utf-8 -*-
import itertools

N,K = map(int,input().split())
l = []*N
l = list(map(int,input().split()))

l_set = list(itertools.combinations(l,K))

max_s = 0
for i in range(len(l_set)):
    l_sum = sum(l_set[i])
    if l_sum>max_s:
        max_s = l_sum

print(max_s)


### FIXED CODE ###

# -*- coding:utf-8 -*-
import itertools
import numpy as np

N,K = map(int,input().split())
l = np.array(list(map(int,input().split())))

ans = 0
for i in range(K):
    max_i = np.argmax(l)
    ans += l[max_i]
    l = np.delete(l,max_i)

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

import sys
input = sys.stdin.readline
from collections import deque
from heapq import heapify, heappush as hpush, heappop as hpop
N, M, L = map(int, input().split())
X = [[] for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    X[a-1].append([b-1, c])
    X[b-1].append([a-1, c])

def dijkstra(n, E, i0=0):
    h = [[0, i0]]
    D = [-1] * n
    done = [0] * n
    D[i0] = 0
    
    while h:
        d, i = hpop(h)
        done[i] = 1
        for j, w in E[i]:
            nd = d + w
            if D[j] < 0 or D[j] >= nd:
                if done[j] == 0:
                    hpush(h, [nd, j])
                    D[j] = nd
    return [d if d >= 0 else 1<<100 for d in D]
def BFS(n, E, i0=0):
    Q = deque([i0])
    D = [-1] * n
    D[i0] = 0
    while Q:
        x = Q.popleft()
        for c in E[x]:
            if D[c] == -1:
                D[c] = D[x] + 1
                Q.append(c)
    return [d if d >= 0 else 1<<100 for d in D]

Y = [[] for _ in range(N)]
for i in range(N):
    D1 = dijkstra(N, X, i)
    for j in range(N):
        if i == j: continue
        if D1[j] <= L:
            Y[i].append(j)

for _ in range(int(input())):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    a = BFS(N, Y, s)[t]-1
    print(a if a < 1 << 50 else -1)
    

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
from collections import deque
N, M, L = map(int, input().split())
D = [[1<<40] * N for _ in range(N)]
for i in range(N):
    D[i][i] = 0
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    D[a][b] = c
    D[b][a] = c

for k in range(N):
    for i in range(N):
        for j in range(N):
            D[i][j] = min(D[i][j], D[i][k] + D[k][j])
Y = [[] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i == j: continue
        if D[i][j] <= L:
            Y[i].append(j)
def BFS(n, E, i0=0):
    Q = deque([i0])
    D = [-1] * n
    D[i0] = 0
    while Q:
        x = Q.popleft()
        for c in E[x]:
            if D[c] == -1:
                D[c] = D[x] + 1
                Q.append(c)
    return D
D2 = []
for i in range(N):
    D2.append(BFS(N, Y, i))

ans = []
for _ in range(int(input())):
    s, t = map(int, input().split())
    a = D2[s-1][t-1]-1
    ans.append(str(a if a >= 0 else -1))
print("\n".join(ans))
### BUGGY CODE ###

K, S = map(int, input().split())

cnt = 0
for i in range(K+1):
    for j in range(K+1):
        for k in range(K+1):
            sum = i + j + k
            if sum == S:
                cnt += 1
                break

print(cnt)


### FIXED CODE ###

K, S = map(int, input().split())

cnt = 0
for i in range(K+1):
    for j in range(K+1):
        if 0 <= (S-i-j) <= K:
            cnt += 1

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

import itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353
def cummax(it, first=-float('inf')):
    """
    np.maximum.accumulate(arr) でもよさそう
    https://stackoverflow.com/questions/33569668/numpy-max-vs-amax-vs-maximum

    累積 max
    :param collections.Iterable it:
    :param float first:
    :return:
    """
    cm = first
    ret = []
    for v in it:
        cm = max(v, cm)
        ret.append(cm)
    return ret


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))

# dp[k]: i | j | k == k となる i, j のうち A[i] + A[j] が最大となる i, j
#: :type: list of ((int, int), (int, int))
dp = [None] * (2 ** N)
for k in range(1, 2 ** N):
    dp[k] = (A[0], 0), (A[k], k)

digits = []
k = 1
while k < 2 ** N:
    digits.append(k)
    k <<= 1

for bit in range(2, N + 1):
    for ds in itertools.combinations(digits, bit):
        k = sum(ds)
        for rm in ds:
            a, b = dp[k - rm]
            c, d = dp[k]
            ss = sorted({a, b, c, d})
            dp[k] = ss[-1], ss[-2]

ans = [0] * (2 ** N)
for k in range(1, 2 ** N):
    (a1, _), (a2, _) = dp[k]
    ans[k] = a1 + a2

ans = cummax(ans[1:])
print(*ans, sep='\n')


### FIXED CODE ###

import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353
def cummax(it, first=-float('inf')):
    """
    np.maximum.accumulate(arr) でもよさそう
    https://stackoverflow.com/questions/33569668/numpy-max-vs-amax-vs-maximum

    累積 max
    :param collections.Iterable it:
    :param float first:
    :return:
    """
    cm = first
    ret = []
    for v in it:
        cm = max(v, cm)
        ret.append(cm)
    return ret


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))
SIZE = 2 ** N

# dp[k]: i | j | k == k となる i, j のうち A[i] + A[j] が最大となる i, j
#: :type: list of ((int, int), (int, int))
dp = [None] * SIZE
for k in range(1, SIZE):
    dp[k] = list(sorted([(A[0], 0), (A[k], k)]))

for k in range(1, SIZE):
    mask = k
    while mask < SIZE - 1:
        # kに立ってないビットを1つだけ立てる
        next_k = (mask + 1) | k
        mask |= next_k

        a1, a2 = dp[k]
        b1, b2 = dp[next_k]
        if a1 > b2:
            # dp[next_k] = a1, a2
            dp[next_k] = dp[k]
        elif b1 > a2:
            # dp[next_k] = b1, b2
            pass
        elif a2 > b2:
            dp[next_k] = b2, a2
        elif b2 > a2:
            dp[next_k] = a2, b2

ans = [0] * SIZE
for k in range(1, SIZE):
    (a1, _), (a2, _) = dp[k]
    ans[k] = a1 + a2

ans = cummax(ans[1:])
print(*ans, sep='\n')
### BUGGY CODE ###

import sys

def parent(i):
    return (i + 1) / 2 - 1

def left(i):
    return 2 * i + 1

def right(i):
    return 2 * i + 2

def sibling(i):
    if i % 2 == 0:
        return i - 1
    else:
        return i + 1

def insert(S, k):
    S.append(k)
    idx = len(S) - 1
    while True:
        p = parent(idx)
        if p < 0 or S[idx] <= S[p]:
            break
        else:
            S[idx], S[p] = S[p], S[idx]
            idx = p
    #print S

def extract(S):
    print S[0]
    S[0] = S[-1]
    S.pop()

    idx = 0
    while True:
        l, r = left(idx), right(idx)
        if l < len(S) and S[idx] < S[l] and (r < len(S) and S[r] <= S[l] or r >= len(S)):
            S[idx], S[l] = S[l], S[idx]
            idx = l
        elif r < len(S) and S[idx] < S[r] and S[l] < S[r]:
            S[idx], S[r] = S[r], S[idx]
            idx = r
        else:
            break
    #print S

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    lines.pop()

    S = []
    for line in lines:
        if line[0] == "i":
            insert(S, int(line[7:]))
        else:
            extract(S)

### FIXED CODE ###

import sys

def insert(k):
    global S, last
    S[last] = k
    idx = last
    while True:
        p = (idx + 1) / 2 - 1
        if S[idx] <= S[p]:
            break
        else:
            S[idx], S[p] = S[p], S[idx]
            idx = p
    last += 1

def maxHeapify(i):
    global S, last
    l = 2 * i + 1
    r = 2 * i + 2

    if l < last and S[l] > S[i]:
        largest = l
    else:
        largest = i

    if r < last and S[r] > S[largest]:
        largest = r

    if largest != i:
        S[i], S[largest] = S[largest], S[i]
        maxHeapify(largest)

def extract():
    global S, last
    print S[0]
    last -= 1
    S[0], S[last] = S[last], 0
    maxHeapify(0)

lines = sys.stdin.readlines()
lines.pop()

S = [0] * 2000001
S[2000000] = 2000000000
last = 0
for line in lines:
    if line[0] == "i":
        insert(int(line[7:]))
    else:
        extract()