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

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

#初期値が0の辞書
from collections import defaultdict
xyz = defaultdict(lambda: set([]))
for _ in range(m):
    x,y,z=map(int,input().split())
    xyz[x].add(y)
    xyz[y].add(x)

checked=set([i for i in range(1,n+1)])

cnt=0
while checked != set([]):
    cnt+=1
    i=checked.pop()
    temp=set([i])
    while len(list(temp))>0:
        v=temp.pop()
        for item in xyz[v]:
            if item in checked:
                checked.remove(item)
                temp.add(item)
                xyz[item].remove(v)

print(cnt)



### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

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

#初期値が0の辞書
from collections import defaultdict
xyz = defaultdict(lambda: set([]))
for _ in range(m):
    x,y,z=map(int,input().split())
    xyz[x].add(y)
    xyz[y].add(x)

no_checked=[0]*n

def DFS(x):
    global no_checked
    global xyz
    no_checked[x-1]=1
    for item in xyz[x]:
        if no_checked[item-1]==0:
            DFS(item)

cnt=0
for i in range(1,n+1):
    if no_checked[i-1]==0:
        cnt+=1
        DFS(i)

    #print(i,no_checked)
print(cnt)
### BUGGY CODE ###

n = int(input())
s = list(sorted(input()) for _ in range(n))

ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        if s[i] == s[j]:
            ans += 1

print(ans)


### FIXED CODE ###

import collections

n = int(input())
s = list(sorted(input()) for _ in range(n))

l = []
for li in s:
    st = ''
    for x in li:
        st += x
    l.append(st)

c = collections.Counter(l)

ans = 0
for x in c.values():
    ans += x * (x - 1) // 2

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

N = int(input())
A = [0] * N
A = list(map(int,input().split()))

ans = 0
mod = 10**9+7
for i in range(N):
    for j in range(i+1,N):
        ans += A[i] * A[j]
        ans %= mod
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
B = [0] * (N+1)

# 累積和を使う
for i in range(1,N+1):
    B[i] = A[i-1]+B[i-1]
# 累積和の配列完成
# print(B) 

ans = 0
MOD = 10**9+7
for i in range(N):
    ans += A[i] * (B[N] - B[i+1])
    ans %= MOD
print(ans)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 7)

INF = 10 ** 9

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

s = []
d = []
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            s.append((i, j))
        else:
            d.append((i, j))

ans = 0
for di in d:
    m = INF
    for si in s:
        m = min(m, abs(di[0] - si[0]) + abs(di[1] - si[1]))
    ans = max(ans, m)
print(ans)


### FIXED CODE ###

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

from collections import deque

lst = deque()

for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            lst.append((i, j, 0))


def chg(i, j):
    if i < 0 or j < 0 or H <= i or W <= j: return False
    if A[i][j] == '.':
        A[i][j] = '#'
        return True
    return False


ans = 0
while lst:
    h, w, v = lst.popleft()
    ans = max(v, ans)
    for i in range(-1, 2):
        for j in range(-1, 2):
            if i != 0 and j != 0: continue

            if chg(h + i, w + j):
                lst.append((h + i, w + j, v + 1))
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
B = sorted(A)
for i in range(N):
    print(A.index(i+1) +1, end =' ')

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = [0] * n
for i in range(n):
  ans[a[i]-1] = i +1
for i in range(n):
  print(ans[i])
### BUGGY CODE ###

import math
A, B, N = map(int, input().split())
maxnum  = 0

for i in range(N+1):
    num = math.floor(A*i/B) - A*math.floor(i/B)
    if num > maxnum:
        maxnum = num
#    print(str(i) + ':' + str(num) + ' max is ' + str(maxnum))
print(maxnum)    


### FIXED CODE ###

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

num = math.floor(A*min(B-1,N)/B) - A*math.floor(min(B-1,N)/B)

print(num)
### BUGGY CODE ###

from math import sqrt

N = int(input())
for i in range(1, N+1):
    ans = 0
    if i <= 5:
        print(0)
        continue
    x = int(sqrt(i-2))+1
    for j in range(1, x):
        for k in range(1, x):
            for l in range(1, x):
                if j**2+k**2+l**2+j*k+k*l+l*j==i:
                    ans += 1
                    break
                elif j**2+k**2+l**2+j*k+k*l+l*j>i:
                    break
    print(ans)

### FIXED CODE ###

from math import sqrt
N = int(input())
if N == 1:
    print(0)
    import sys
    sys.exit()
ans = [0] * (N+1)
x = int(sqrt(N-2))+1
for j in range(1, x):
    for k in range(1, x):
        for l in range(1, x):
            y = j**2+k**2+l**2+j*k+k*l+l*j
            if y <= N:
                ans[y] += 1
for n in ans[1:N+1]:
    print(n)
### BUGGY CODE ###

n,a,b=map(int,input().split())
t=[]
for i in range(n):
    t.append(int(input()))
t=set(t)
ans=len(t)
for i in range(a,b):
    if i in t:
        ans-=1
print(ans)

### FIXED CODE ###

import bisect
n,a,b=map(int,input().split())
t=set([])
for i in range(n):
    t.add(int(input()))
t=list(t)
t.sort()
ai=bisect.bisect_left(t,a)
bi=bisect.bisect_left(t,b)
print(len(t)-(bi-ai))
### BUGGY CODE ###

n,m = map(int,input().split())
f = [False for _ in range(n)]
a = [[] for _ in range(n)]
res = 0


for _ in range(m):
    x,y,z = map(int,input().split())
    a[x-1].append(y-1)
    a[y-1].append(x-1)

for i in range(n):
    if not f[i]:
        res += 1
        q=[]
        q.append(i)
        while q:
            t = q.pop()
            f[t] = True
            for g in a[t]:
                if not f[g]:
                    q.append(g)
print(res)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
n,m = map(int,input().split())
f = [False for _ in range(n)]
a = [[] for _ in range(n)]
res = 0

def dfs(k):
    f[k] = True
    for g in a[k]:
        if not f[g]:
            dfs(g)

for _ in range(m):
    x,y,z = map(int,input().split())
    a[x-1].append(y-1)
    a[y-1].append(x-1)

for i in range(n):
    if not f[i]:
        res += 1
        dfs(i)
print(res)
### BUGGY CODE ###

#coding:utf-8
import sys
import bisect
import math
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = True
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]

    n, k = LMIIS()
    aa = LMIIS()
    ff = LMIIS()
    aa.sort(reverse=True)
    ff.sort()
    a = tuple(aa)
    f = tuple(ff)


    max_ = 10**12
    min_ = 0

    while max_ != min_ + 1:
        x = (max_ + min_) // 2
        shugyo = 0
        for i in range(n):
            shugyo += max(0, a[i] - x // f[i])

        if shugyo <= k:
            max_ = x
        else:
            min_ = x


    if x == min_:
        x += 1
    if sum(a) <= k:
        x = 0
    print(x)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#coding:utf-8
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = True
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]

    n, k = LMIIS()
    aa = LMIIS()
    ff = LMIIS()
    aa.sort(reverse=True)
    ff.sort()
    a = tuple(aa)
    f = tuple(ff)


    max_ = 10**12
    min_ = 0

    while max_ != min_ + 1:
        x = (max_ + min_) // 2
        shugyo = 0
        for i in range(n):
            shugyo += max(0, a[i] - x // f[i])

        if shugyo <= k:
            max_ = x
        else:
            min_ = x


    if x == min_:
        x += 1
    if sum(a) <= k:
        x = 0
    print(x)

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

h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1-1, y1-1, x2-1, y2-1

m = [[-1] * w for _ in range(h)]
for hh in range(h):
    c = input()
    for ww, cc in enumerate(c):
        if cc == '.':
            m[hh][ww] = h*w

from collections import deque
q = deque()

q.append((0, x1, y1))
while q:
    s, x, y = q.popleft()

    for i in range(1, k+1):
        xx, yy = x + i, y
        if xx >= h or m[xx][yy] == -1:
            break
        if m[xx][yy] <= s+1:
            continue
        if xx == x2 and yy == y2:
            print(s+1)
            exit(0)
        m[xx][yy] = s+1
        q.append((s+1, xx, yy))

    for i in range(1, k+1):
        xx, yy = x - i, y
        if xx < 0 or m[xx][yy] == -1:
            break
        if m[xx][yy] <= s+1:
            continue
        if xx == x2 and yy == y2:
            print(s+1)
            exit(0)
        m[xx][yy] = s+1
        q.append((s+1, xx, yy))

    for i in range(1, k+1):
        xx, yy = x, y + i
        if yy >= w or m[xx][yy] == -1:
            break
        if m[xx][yy] <= s+1:
            continue
        if xx == x2 and yy == y2:
            print(s+1)
            exit(0)
        m[xx][yy] = s+1
        q.append((s+1, xx, yy))

    for i in range(1, k+1):
        xx, yy = x, y - i
        if yy < 0 or m[xx][yy] == -1:
            break
        if m[xx][yy] <= s+1:
            continue
        if xx == x2 and yy == y2:
            print(s+1)
            exit(0)
        m[xx][yy] = s+1
        q.append((s+1, xx, yy))

print(-1)


### FIXED CODE ###

h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
x1, y1, x2, y2 = x1-1, y1-1, x2-1, y2-1

m = [[-1] * w for _ in range(h)]
for hh in range(h):
    c = input()
    for ww, cc in enumerate(c):
        if cc == '.':
            m[hh][ww] = h*w

from collections import deque
q = deque()

q.append((0, x1, y1))
while q:
    s, x, y = q.popleft()
    s1 = s + 1

    for i in range(1, k+1):
        xx, yy = x + i, y
        if xx >= h or m[xx][yy] <= s:
            break
        if m[xx][yy] == s1:
            continue
        if xx == x2 and yy == y2:
            print(s1)
            exit(0)
        m[xx][yy] = s1
        q.append((s1, xx, yy))

    for i in range(1, k+1):
        xx, yy = x - i, y
        if xx < 0 or m[xx][yy] <= s:
            break
        if m[xx][yy] == s1:
            continue
        if xx == x2 and yy == y2:
            print(s1)
            exit(0)
        m[xx][yy] = s1
        q.append((s1, xx, yy))

    for i in range(1, k+1):
        xx, yy = x, y + i
        if yy >= w or m[xx][yy] <= s:
            break
        if m[xx][yy] == s1:
            continue
        if xx == x2 and yy == y2:
            print(s1)
            exit(0)
        m[xx][yy] = s1
        q.append((s1, xx, yy))

    for i in range(1, k+1):
        xx, yy = x, y - i
        if yy < 0 or m[xx][yy] <= s:
            break
        if m[xx][yy] == s1:
            continue
        if xx == x2 and yy == y2:
            print(s1)
            exit(0)
        m[xx][yy] = s1
        q.append((s1, xx, yy))

print(-1)
### BUGGY CODE ###

ii=lambda:map(int,raw_input().split())
n,k=ii()
e=[[] for _ in range(n)]
for _ in range(n-1):
    a,b=ii()
    e[a-1]+=[b-1];e[b-1]+=[a-1]
cost=[0]*n
ans=10**5
visit=[0]
def dfs(x,f):
    global visit
    del visit[:]
    visit+=[f]
    q=[(x,0)]
    while len(q):
        v,c=q.pop(0);cost[v]=c;visit+=[v]
        for w in e[v]:
            if w not in visit:q+=[(w,c+1)]
    return len([i for i in cost if i>k/2])
if k%2:
    for i in range(n):
        for j in e[i]:
            if i<j:dfs(i,j);ans=min(ans,dfs(j,i))
    print ans
else:
    for i in range(n):
        ans=min(ans,dfs(i,-1))
    print ans


### FIXED CODE ###

ii=lambda:map(int,raw_input().split())
n,k=ii()
T,F=True,False
e=[[] for _ in range(n)]
for _ in range(n-1):
    a,b=ii()
    e[a-1]+=[b-1];e[b-1]+=[a-1]
cost=[0]*n
ans=10**5
def dfs(x,f):
    if f>=0:vis[f]=T
    q=[(x,0)]
    while len(q):
        v,c=q.pop(0)
        if c>k/2:break
        cost[v]=c;vis[v]=T
        for w in e[v]:
            if not vis[w]:q+=[(w,c+1)]
    return n-vis.count(T)
if k%2:
    for i in range(n):
        for j in e[i]:
            if i<j:vis=[F]*n;dfs(i,j);ans=min(ans,dfs(j,i))
else:
    for i in range(n):vis=[F]*n;ans=min(ans,dfs(i,-1))
print ans
### BUGGY CODE ###

import sys

dp=[[0]*2019 for _ in range(2)]
dig=[int(c) for c in sys.stdin.readline().strip()]

p=0
cnt=0
for x in dig:
    np=(p+1)&1
    for i in range(2019):
        dp[np][(i*10+x)%2019]=dp[p][i]
    dp[np][x]+=1
    p=np
    cnt+=dp[p][0]

print(cnt)

### FIXED CODE ###

from collections import Counter
S=input()[::-1]

X=[0]
md=2019

for i,s in enumerate(S):
    X.append((X[-1]+int(s)*pow(10,i,md))%md)

C=Counter(X)
ans=0
for v in C.values():
    ans+=v*(v-1)//2

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

from bisect import bisect_left

n = int(input())
l = sorted(list(map(int, input().split())))

ans = 0
for i in range(len(l)):
    for j in range(len(l))[i + 1:]:
        k = bisect_left(l[j:], l[i] + l[j]) + j
        ans += len(l[j:k]) - 1
print(ans)


### FIXED CODE ###

from bisect import bisect_left
 
n = int(input())
l = sorted(list(map(int,input().split())))

ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        k = bisect_left(l,l[i]+l[j])
        ans += k - j - 1

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

S=list(input())
MOD=10**9+7
dp=[0]*13
dp[0]=1
for i in range(1,len(S)+1):
    ans=[0]*13
    if S[-i]=="?":
        for j in range(10):
            a=(j*10**(i-1))%13
            for k in range(13):
                ans[(k+a)%13]=ans[(k+a)%13]+dp[k]
    else:
        a=int(S[-i])
        a=(a*10**(i-1))%13
        for k in range(13):
            ans[(k+a)%13]=ans[(k+a)%13]+dp[k]
    dp=ans.copy()
print(ans[5]%MOD)

### FIXED CODE ###

S=input()
MOD=10**9+7
dp=[[0]*13 for i in range(len(S)+1)]
dp[0][0]=1
for i in range(len(S)):
    if S[i]=="?":
        for j in range(10):
            for k in range(13):
                dp[i+1][(10*k+j)%13]+=dp[i][k]%MOD
    else:
        a=int(S[i])
        for k in range(13):
            dp[i+1][(10*k+a)%13]+=dp[i][k]%MOD
print(dp[len(S)][5]%MOD)
### BUGGY CODE ###

import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
import collections


n,x,y = map(int,input().split())

route = np.array([[0 for _ in range(n)]for _ in range(n)])
for i in range(n-1):
	route[i][i+1] = 1

route[x-1][y-1] = 1
route[y-1][x-1] = 1

#res = shortest_path(route, unweighted=False,directed=False)
res = dijkstra(route, directed=False)

tmp = []
for i in range(n):
	tmp.append(collections.Counter(res[i][i:]))


ans = [0 for _ in range(n)]
for i in range(n):
	for k in range(1,n):
		ans[k] += tmp[i][k]

for i in range(1,n):
	print(ans[i])


### FIXED CODE ###

from scipy.sparse.csgraph import dijkstra
import sys
def main():
	input = sys.stdin.readline

	n,x,y = map(int,input().split())

	route = [[0 for _ in range(n)]for _ in range(n)]
	for i in range(n-1):
		route[i][i+1] = 1

	route[x-1][y-1] = 1
	route[y-1][x-1] = 1
	route = tuple(route)
	#res = shortest_path(route, unweighted=False,directed=False)
	res = tuple(dijkstra(route, directed=False))

	ans = [0 for _ in range(n)]
	for i in range(n):
		for j in range(i,n):
			ans[int(res[i][j])] += 1

	for i in range(1,n):
		print(ans[i])
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys


def solve():
    N, K, *H = map(int, sys.stdin.read().split())
    dp = [10**10] * N
    dp[0] = 0
    for i, h in enumerate(H):
        dp_i = dp[i]
        for k, dp_i_k in enumerate(dp[i+1:i+K+1], start=1):
            if i+k > N-1:
                break
            tmp_dp = dp_i + abs(h - H[i+k])
            if dp_i_k > tmp_dp:
                dp[i+k] = tmp_dp
    return dp[-1]


if __name__ == "__main__":
    answer = solve()
    print(answer)


### FIXED CODE ###

import sys


def solve():
    N, K, *H = map(int, sys.stdin.read().split())
    dp = [0] * N
    for i in range(1, N):
        s = i-K if i-K > 0 else 0
        dp[i] = min(dp[j] + abs(H[i] - H[j]) for j in range(s, i))
    return dp[-1]


if __name__ == "__main__":
    answer = solve()
    print(answer)
### BUGGY CODE ###

N = int(input())
s = list(input())

ans = 0
for i in range(1000):
    t = str(i).zfill(3)
    t_index = 0
    for s_index in range(N):
        if s[s_index] == t[t_index]:
            t_index += 1
            if t_index == 3:
                break
    if t_index == 3:
        ans += 1
print(ans)

### FIXED CODE ###

from collections import defaultdict
n = int(input())
S = input()

d1 = defaultdict(int)
d2 = defaultdict(int)
d3 = defaultdict(int)

for s in S:
    for x in d2:
        d3[x+s]+=1
    for y in d1:
        d2[y+s]+=1
    d1[s]+=1

print(len(d3))
### BUGGY CODE ###

import math
import sys
input = sys.stdin.readline

L, R = map(int, input().split())
min_mod = float('inf')
for i in range(L, R + 1):
    for j in range(i + 1, R + 1):
        mod = (i * j) % 2019
        if mod < min_mod:
            min_mod = mod
print(min_mod)


### FIXED CODE ###

l, r = [int(i) for i in input().split()]
ans = 2020
for i in range(l, r):
    for j in range(i + 1, r + 1):
        ans = min(ans, (i * j) % 2019)
        if ans == 0:
            print(ans)
            exit()
print(ans)
### BUGGY CODE ###

from math import ceil
INF = float('inf')
d, g = map(int, input().split())
data = [list(map(int, input().split())) for _ in range(d)]
def f(data, score, targets):
  if score <= 0:
    return 0
  result = INF
  for i in targets:
    t = ceil(score / ((i + 1) * 100))
    if t < data[i][0] and t < result:
      result = t
  for i in range(len(targets)):
    j = targets[i]
    p, c = data[j]
    t = p + f(data, score - (j + 1) * 100 * p - c, targets[0:i] + targets[i + 1:])
    if t < result:
      result = t
  return result
print(f(data, g, list(range(len(data)))))


### FIXED CODE ###

INF = float('inf')
d, g = map(int, input().split())
data = []
for i in range(d):
  p, c = map(int, input().split())
  data.append([p, c, (i + 1) * 100, (i + 1) * 100 * p + c])
def f(data, total, targets):
  if total <= 0:
    return 0
  result = INF
  for i in targets:
    score = data[i][2]
    t = (total + score - 1) // score
    if t < data[i][0] and t < result:
      result = t
  for i in range(len(targets)):
    j = targets[i]
    p, c, score, subtotal = data[j]
    t = p + f(data, total - subtotal, targets[0:i] + targets[i + 1:])
    if t < result:
      result = t
  return result
print(f(data, g, list(range(len(data)))))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from itertools import accumulate

n, m, q = map(int, input().split())
S = [[0]*(m+1)] + [[0] + list(map(int, list(input().rstrip()))) for _ in range(n)]
B = [[0]*(m+1) for _ in range(n+1)]
U = [[0]*(m+1) for _ in range(n+1)]
L = [[0]*(m+1) for _ in range(n+1)]
for i in range(1, n+1):
  for j in range(1, m+1):
    if S[i][j]:
      U[i][j] = S[i-1][j]
      L[i][j] = S[i][j-1]
for i in range(1, n+1):
  B[i] = list(accumulate(S[i]))
  U[i] = list(accumulate(U[i]))
  L[i] = list(accumulate(L[i]))
B = list(zip(*B))
U = list(zip(*U))
L = list(zip(*L))
for j in range(1, m+1):
  B[j] = list(accumulate(B[j]))
  U[j] = list(accumulate(U[j]))
  L[j] = list(accumulate(L[j]))
B = list(zip(*B))
U = list(zip(*U))
L = list(zip(*L))
def calc_b(x1, y1, x2, y2):
  return B[x2][y2] - B[x1-1][y2] - B[x2][y1-1] + B[x1-1][y1-1]
def calc_u(x1, y1, x2, y2):
  return U[x2][y2] - U[x1][y2] - U[x2][y1-1] + U[x1][y1-1]
def calc_l(x1, y1, x2, y2):
  return L[x2][y2] - L[x1-1][y2] - L[x2][y1] + L[x1-1][y1]

for _ in range(q):
  x1, y1, x2, y2 = map(int, input().split())
  res = calc_b(x1, y1, x2, y2) - (calc_u(x1, y1, x2, y2) + calc_l(x1, y1, x2, y2))
  print(res)

### FIXED CODE ###

import sys
input = sys.stdin.readline

n, m, q = map(int, input().split())
S = [[0]*(m+1)] + [[0] + list(map(int, list(input().rstrip()))) for _ in range(n)]
B = [[0]*(m+1) for _ in range(n+1)]
U = [[0]*(m+1) for _ in range(n+1)]
L = [[0]*(m+1) for _ in range(n+1)]
for i in range(1, n+1):
  for j in range(1, m+1):
    B[i][j] = B[i-1][j] + B[i][j-1] - B[i-1][j-1] + S[i][j]
    U[i][j] = U[i-1][j] + U[i][j-1] - U[i-1][j-1] + U[i][j]
    L[i][j] = L[i-1][j] + L[i][j-1] - L[i-1][j-1] + L[i][j]
    if S[i][j]:
      U[i][j] += S[i-1][j]
      L[i][j] += S[i][j-1]
    
def calc_b(x1, y1, x2, y2):
  return B[x2][y2] - B[x1-1][y2] - B[x2][y1-1] + B[x1-1][y1-1]
def calc_u(x1, y1, x2, y2):
  return U[x2][y2] - U[x1][y2] - U[x2][y1-1] + U[x1][y1-1]
def calc_l(x1, y1, x2, y2):
  return L[x2][y2] - L[x1-1][y2] - L[x2][y1] + L[x1-1][y1]

for _ in range(q):
  x1, y1, x2, y2 = map(int, input().split())
  res = calc_b(x1, y1, x2, y2) - (calc_u(x1, y1, x2, y2) + calc_l(x1, y1, x2, y2))
  print(res)
### BUGGY CODE ###

from collections import defaultdict as dd
N = int(input())
dic=dd(int)
for x in range(1,N+1):
    t1 = N-x**2
    if t1 <= 1:
        continue
    for y in range(1,t1+1):
        t2 = N-x**2-y**2
        if t2 <= 0:
            continue
        for z in range(1,t2+1):
            dic[x**2+y**2+z**2+x*y+y*z+z*x] += 1
for i in range(N):
    print(dic[i+1])



### FIXED CODE ###

from collections import defaultdict as dd
N = int(input())
dic=dd(int)
for x in range(1,N+1):
    t1 = N-x**2
    if t1 <= 1:
        continue
    for y in range(1,t1+1):
        t2 = N-x**2-y**2
        if t2 <= 0:
            continue
        for z in range(1,t2+1):
            tmp = x**2+y**2+z**2+x*y+y*z+z*x
            if tmp > N:
                break
            else:
                dic[tmp] += 1

for i in range(N):
    print(dic[i+1])
### BUGGY CODE ###

from heapq import heappop,heappush
def resolve():
    N = int(input())
    b = 0
    left = []
    right = []
    sumleft = sumright = mid = 0
    for _ in range(N):
        q = list(map(int,input().split()))
        if q[0]==1:#登録
            a = q[1]
            b = b + q[2]
            if not left or -left[0]>a:
                heappush(left,-a)
                sumleft = sumleft + a
                if (len(left)-len(right))>=2:
                    move = -heappop(left)
                    heappush(right,move)
                    sumleft = sumleft-move
                    sumright = sumright+move
            else:
                heappush(right,a)
                sumright = sumright + a
                if len(left)<len(right):
                    move = heappop(right)
                    heappush(left,-move)
                    sumright = sumright-move
                    sumleft = sumleft+move
            mid = -left[0]
        else:#表示
            ans = (len(left)-len(right))*mid-sumleft+sumright + b
            print(mid,ans)


if __name__ == "__main__":
    resolve()

### FIXED CODE ###

from heapq import heappop,heappush
import sys
input = sys.stdin.readline
def resolve():
    N = int(input())
    b = 0
    left = []
    right = []
    sumleft = sumright = mid = 0
    for _ in range(N):
        q = list(map(int,input().split()))
        if q[0]==1:#登録
            a = q[1]
            b = b + q[2]
            if not left or -left[0]>a:
                heappush(left,-a)
                sumleft = sumleft + a
                if (len(left)-len(right))>=2:
                    move = -heappop(left)
                    heappush(right,move)
                    sumleft = sumleft-move
                    sumright = sumright+move
            else:
                heappush(right,a)
                sumright = sumright + a
                if len(left)<len(right):
                    move = heappop(right)
                    heappush(left,-move)
                    sumright = sumright-move
                    sumleft = sumleft+move
            mid = -left[0]
        else:#表示
            ans = (len(left)-len(right))*mid-sumleft+sumright + b
            print(mid,ans)


if __name__ == "__main__":
    resolve()