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

from collections import Counter
import heapq
n ,k = map(int, input().split())

used = []
unused = []
for i in range(n):
    t, d = map(int, input().split())
    unused.append((-d,t))
heapq.heapify(unused)
# 最初の集合
c = Counter()
ans = []
kiso = 0
for i in range(k):
    d, t = heapq.heappop(unused)
    kiso -= d
    c[t] += 1
    heapq.heappush(used,(-d, t))
bonus = len(c)
ans.append(kiso + bonus**2)

for i in range(k):
    # いらないものを抜く
    flag = False
    atode = []
    while used:
        d, t = heapq.heappop(used)
        if c[t] > 1:
            c[t] -= 1
            kiso -= d
            flag = True
            break
        atode.append((d,t))
    for i in atode:
        heapq.heappush(used, i)
    # 全部の種類が1つしかない場合
    if not flag:break
    # 種類を増やす
    flag = False
    atode = []
    while unused:
        d, t = heapq.heappop(unused)
        if c[t]==0:
            bonus+=1
            kiso += -d
            c[t] += 1
            heapq.heappush(used, (-d, t))
            flag = True
            break
        atode.append((d,t))
    for i in atode:
        heapq.heappush(unused, i)
    # 種類を増やせなかった場合
    if not flag:break
    ans.append(kiso + bonus**2)
print(max(ans))

### FIXED CODE ###

#参考 https://atcoder.jp/contests/abc116/submissions/4059000
n, k = map(int,input().split())
# 価値の大きい順にソート, おいしさが前に来るようにした
sushi = sorted(list(map(int, input().split()))[::-1] for i in range(n))[::-1]
s = set()
# 二個以上あるものの集合があれば良い,かつ最小順
q = []
kiso = 0
for i in range(k):
    d, t = sushi[i]
    if t in s:
        q.append(d)
    else:
        s.add(t)
    kiso += d
ans = kiso + len(s)**2

# 減らせる ∧ 増やせる
i = k
while i < n and q:
    d, t = sushi[i]
    if t not in s:
        s.add(t)
        kiso += -q.pop()+d
        ans = max(ans, kiso+len(s)**2)
        continue
    i+=1
print(ans)
### BUGGY CODE ###

import itertools
n = int(input())
S = list(input())
sl = itertools.combinations(S, 3)
sl_s = set(sl)
print(len(sl_s))

### FIXED CODE ###

n = int(input())
s = input()
ans = 0
for i in range(1000):
    tg = str(i + 1000)[1:]
    if tg[0] not in s:
        continue
    else:
        x2 = s[s.index(tg[0]) + 1:]
        if tg[1] not in x2:
            continue
        else:
            x3 = x2[x2.index(tg[1]) + 1:]
            if tg[2] not in x3:
                continue
            else:
                ans += 1
print(ans)
### BUGGY CODE ###

s = input()
q = int(input())
rv = False
for i in range(q):
    t = input().split(' ')
    if t[0] == '1':
        rv = True if not rv else False
    else:
        if t[1] == '1' and not rv or t[1] == '2' and rv:
            s = t[2] + s
        else:
            if t[1] == '1' and rv or t[1] == '2' and not rv:
                s = s + t[2]
print(s if not rv else s[::-1])

### FIXED CODE ###

from collections import deque
s = list(input())
q = int(input())
rv = False
fr = deque()
re = []
for i in range(q):
    t = input().split(' ')
    if t[0] == '1':
        rv = True if not rv else False
    else:
        if t[1] == '1' and not rv or t[1] == '2' and rv:
            fr.appendleft(t[2])
        else:
            if t[1] == '1' and rv or t[1] == '2' and not rv:
                re.append(t[2])
if rv:
    re.reverse()
    s.reverse()
    fr.reverse()
    print(''.join(re + s) + ''.join(fr))
else:
    print(''.join(fr) + ''.join(s + re))
### BUGGY CODE ###

def main():
  r1,c1,r2,c2 = map(int,input().split())

  mod = 10**9+7

  fact = [1,1]
  finv = [1,1]
  inv = [0,1]

  for i in range(2,2*10**6+1):
    fact.append((fact[-1]*i)%mod)
    inv.append((inv[mod%i]*(mod-mod//i))%mod)
    finv.append((finv[-1]*inv[-1])%mod)

  def nCr(n,r,mod):
      if (r < 0) or (n < r):
          return 0
      r = min(r, n - r)
      return fact[n]*finv[r]*finv[n-r]%mod

  print((nCr(r2+c2+2,r2+1,mod)+nCr(r1+c1,r1,mod)-nCr(c2+r1+1,r1,mod)-nCr(r2+c1+1,c1,mod))%mod)

if __name__ == "__main__":
  main()

### FIXED CODE ###

def main():
  r1,c1,r2,c2 = map(int,input().split())

  mod = 10**9+7

  fact = [1,1]
  finv = [1,1]
  inv = [0,1]

  for i in range(2,r2+c2+3):
    fact.append((fact[-1]*i)%mod)
    inv.append((inv[mod%i]*(mod-mod//i))%mod)
    finv.append((finv[-1]*inv[-1])%mod)

  def nCr(n,r,mod):
      
      return fact[n]*finv[r]*finv[n-r]%mod

  print((nCr(r2+c2+2,r2+1,mod)+nCr(r1+c1,r1,mod)-nCr(c2+r1+1,r1,mod)-nCr(r2+c1+1,c1,mod))%mod)

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

n,m=map(int,input().split(" "))
l=[]
bone=[]
ans=False
for i in range(m):
	a,b=map(int,input().split(" "))
	if a==1:l.append(b)
	if b==n:bone.append(a)
	
for i in l:
	for j in bone:
		if i == j:
			ans=True
	
if ans == True:print("POSSIBLE")
else:print("IMPOSSIBLE")


### FIXED CODE ###

n,m=map(int,input().split(" "))
l=[]
bone=[]
for i in range(m):
		a,b=input().split(" ")
		if a=="1":l.append(b)
		if b==str(n):bone.append(a)

ans=list(set(l) & set(bone))
if len(ans)!=0:
	print("POSSIBLE")
else:			
	print("IMPOSSIBLE")
### BUGGY CODE ###

N,M=map(int,input().split())
S=list(map(int,input().split()))
T=list(map(int,input().split()))

data=[[0 for i in range(0,M)] for j in range(0,N)]
for i in range(0,N):
    if S[i]==T[0]:
        data[i][0]=1

dp=[[1 for i in range(0,M)] for j in range(0,N)]
for j in range(0,M):
    if j==0:
        if S[0]==T[0]:
            dp[0][0]=2
    else:
        if S[0]==T[j]:
            dp[0][j]=(dp[0][j-1]+1)
        else:
            dp[0][j]=dp[0][j-1]

for i in range(0,N):
    for j in range(0,M):
        if j!=0:
            if S[i]==T[j]:
                data[i][j]=(data[i][j-1]+dp[i-1][j-1])
            else:
                data[i][j]=data[i][j-1]
        if i!=0:
            dp[i][j]=(dp[i-1][j]+data[i][j])

print(dp[N-1][M-1]%(10**9+7))

### FIXED CODE ###

N,M=map(int,input().split())
S=list(map(int,input().split()))
T=list(map(int,input().split()))

data=[[0 for i in range(0,M)] for j in range(0,N)]
for i in range(0,N):
    if S[i]==T[0]:
        data[i][0]=1

dp=[[1 for i in range(0,M)] for j in range(0,N)]
for j in range(0,M):
    if j==0:
        if S[0]==T[0]:
            dp[0][0]=2
    else:
        if S[0]==T[j]:
            dp[0][j]=(dp[0][j-1]+1)%(10**9+7)
        else:
            dp[0][j]=dp[0][j-1]%(10**9+7)

for i in range(0,N):
    for j in range(0,M):
        if j!=0:
            if S[i]==T[j]:
                data[i][j]=(data[i][j-1]+dp[i-1][j-1])%(10**9+7)
            else:
                data[i][j]=data[i][j-1]
        if i!=0:
            dp[i][j]=(dp[i-1][j]+data[i][j])%(10**9+7)

print(dp[N-1][M-1]%(10**9+7))
### BUGGY CODE ###

import bisect


class SegTree:

    def __init__(self, N):
        self.N = N
        self.data = [0] * (2 * N)

    def update(self, i, x):
        i += self.N - 1
        self.data[i] = x
        while i > 0:
            i = (i - 1) // 2
            v = self.data[2 * i + 1] + self.data[2 * i + 2]
            self.data[i] = v

    def query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        if a <= l and r <= b:
            return self.data[k]
        else:
            v = self.query(a, b, 2 * k + 1, l, (l + r) // 2)
            w = self.query(a, b, 2 * k + 2, (l + r) // 2, r)
            return v + w


def main():
    N, D, A = list(map(int, input().split(' ')))
    pw2_N = 1
    while pw2_N < N:
        pw2_N *= 2
    monsters = [list(map(int, input().split(' '))) for _ in range(N)]
    monsters.sort()
    if N == 1:
        print((monsters[0][1] + A - 1) // A)
        return
    counts = [(h + A - 1) // A for _, h in monsters]
    X = [x for x, _ in monsters]
    diffs = [(counts[i] - counts[i - 1]) if i > 0 else counts[i] for i in range(N)]
    tree = SegTree(pw2_N)
    for i, d in enumerate(diffs):
        tree.update(i, d)
    ans = 0
    for i in range(N):
        ci = tree.query(0, i + 1, 0, 0, pw2_N)
        if ci <= 0:
            continue
        ans += ci
        r = X[i] + 2 * D
        j = bisect.bisect_right(X, r)
        di = tree.query(i, i + 1, 0, 0, pw2_N)
        dj = tree.query(j, j + 1, 0, 0, pw2_N)
        tree.update(i, di - ci)
        tree.update(j, dj + ci)
    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import bisect


def main():
    N, D, A = list(map(int, input().split()))
    monsters = [list(map(int, input().split())) for _ in range(N)]
    monsters.sort()
    X = [m[0] for m in monsters]
    # 端から貪欲に攻撃していく
    ans = 0
    damages = [0] * (N + 1)
    for n, monster in enumerate(monsters):
        x, h = monster
        h = max(0, h - damages[n])
        to_n = bisect.bisect_right(X, x + 2 * D)
        cnt = (h + A - 1) // A  # ceil(h / A)
        ans += cnt
        damages[n] += A * cnt
        damages[to_n] -= A * cnt
        damages[n + 1] += damages[n]
    print(ans)


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

import sys
import time

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(input())
    a = list(map(int, readline().split()))

    import networkx as nx
    G = nx.Graph()

    for _ in range(n - 1):
        u, v = map(int, readline().split())
        u, v = u - 1, v - 1
        G.add_edge(u, v)

    ans = [0] * n
    dp = [INF] * n
    dp[0] = a[0]

    from collections import deque, namedtuple
    import bisect

    stack = deque()
    Params = namedtuple("Params", ["node", "dp_index", "prev_value", "new_value"])
    par = 0
    stack.append(Params(0, 0, INF, a[0]))

    for prev, cur in nx.algorithms.edge_dfs(G, source=0):
        if par != prev:
            while stack:
                params = stack.pop()
                if params.node == prev:
                    stack.append(params)
                    break
                ans[params.node] = bisect.bisect_left(dp, INF)
                dp[params.dp_index] = params.prev_value
        new_val = a[cur]
        index = bisect.bisect_left(dp, new_val)
        prev_val = dp[index]
        dp[index] = new_val
        stack.append(Params(cur, index, prev_val, new_val))
        par = cur

    while stack:
        params = stack.pop()
        ans[params.node] = bisect.bisect_left(dp, INF)
        dp[params.dp_index] = params.prev_value

    print(*ans, sep="\n")


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import time

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10**5)


def main():
    n = int(input())
    a = list(map(int, readline().split()))
    node = {i: [] for i in range(n)}

    for _ in range(n - 1):
        u, v = map(int, readline().split())
        u, v = u - 1, v - 1
        node[u].append(v)
        node[v].append(u)

    ans = [0] * n
    dp = [INF] * n
    dp[0] = a[0]
    visited = [False] * n

    from collections import deque
    import bisect

    def dfs(cur):
        visited[cur] = True
        nv = a[cur]
        index = bisect.bisect_left(dp, nv)
        pv = dp[index]
        dp[index] = nv
        suc = node[cur]

        for nx in suc:
            if not visited[nx]:
                dfs(nx)

        ans[cur] = bisect.bisect_left(dp, INF)
        dp[index] = pv

    dfs(0)
    print(*ans, sep="\n")


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

from collections import* #defaultdict Counter deque appendleft
import sys
input=sys.stdin.readline
import functools
@functools.lru_cache(maxsize=None)

def main():
    n=int(input())
    d=defaultdict(deque)
    for i in range(n):
        d[i+1]=deque(map(int,input().split()))

    c=0
    immortalskip=set()
    while any(d.values()):
        c+=1
        f=0
        skip=set()
        for i in range(1,n+1):
            if i not in skip.copy():
                if d[i]:
                    if d[i][0] in skip:
                        continue
                    elif i==d[d[i][0]][0]:
                        oppo=d[i].popleft()
                        d[oppo].popleft()
                        skip.add(oppo)
                        skip.add(i)
                        f=1
                        
                else:
                    skip.add(i)
        if not f:
            print(-1)
            exit()

    print(c)

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import* #defaultdict Counter deque appendleft
import sys
input=sys.stdin.readline
import time
t=time.time()

def main():
    n=int(input())
    d=[[]]+[deque(map(int,input().split()))for i in n*[0]]

    c=0
    while any(d):
        c+=1
        f=0
        skip=set()
        for i in range(1,n+1):
            if i not in skip:
                if d[i]:
                    if d[i][0] in skip:
                        continue
                    elif i==d[d[i][0]][0]:
                        oppo=d[i].popleft()
                        d[oppo].popleft()
                        skip.add(oppo)
                        skip.add(i)
                        f=1

        if not f:
            print(-1)
            exit()
        if abs(time.time()-t)>1:
            print(n*(n-1)//2)
            exit()

    print(c)

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

n = int(input())
ls = list(map(int, input().split()))

resultk = 1
for i in range(n):
  resultk = resultk * ls[i]

r = resultk


if r > 10 ** 18:
  print(-1)
else:
  print(r)

### FIXED CODE ###

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

ans = 1

if 0 in A:
  ans = 0
else:
  for i in range(N):
    ans *= A[i]
    i += 1
    if ans > 10**18:
      ans = -1
      break

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

# K回前と現在の問いが同じだったら0点

str1 = input().split(" ")
str2 = input().split(" ")
t = input()

n = int(str1[0])
k = int(str1[1])

r = int(str2[0])
s = int(str2[1])
p = int(str2[2])

result = 0
douchilist = []
for i in range(0,n):
    if i >= k:
        if t[i] == t[i-k] and i-k not in douchilist:
            result += 0
            douchilist.append(i)
            continue

    if t[i] == "r":
        result += p
        continue

    if t[i] == "s":
        result += r
        continue

    if t[i] == "p":
        result += s
        continue


print(result)

### FIXED CODE ###

# K回前と現在の問いが同じだったら0点

str1 = input().split(" ")
str2 = input().split(" ")
t = list(input())

n = int(str1[0])
k = int(str1[1])

r = int(str2[0])
s = int(str2[1])
p = int(str2[2])

result = 0
hoge = 0
for i in range(0,n):
    if i < k:
        continue

    j = i-k
    if t[i] == t[j]:
        t[i] = "_"

pres = p * t.count("r")
rres = r * t.count("s")
sres = s * t.count("p")

print(pres + rres + sres)
### BUGGY CODE ###

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

while len(A)!=1:
#for i in range(2):
    A.sort()
    for i in range(len(A)-1):
        if A.count(0):
            A.remove(0)
            break
        A[i+1]=A[i+1]%A[0]

print(max(A))

### FIXED CODE ###

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

def gcd(a,b):
    while b:
        a,b=b,a%b
    return a

A.sort()
y=A[0]
for i in range(1,N):
    y=gcd(y,A[i])
print(y)
### BUGGY CODE ###

K = input()
D = int(input())
L = len(K)
MOD = 10**9+7
dp = [[[0]*D for j in range(2)] for i in range(L+1)] #dp[i][less][modD]
dp[0][0][0] = 1
for i,c in enumerate(K):
    for less in range(2):
        lim = 9 if less else int(c)
        for r in range(D):
            for d in range(lim+1):
                dp[i+1][less or d < lim][(r+d)%D] += dp[i][less][r]
                dp[i+1][less or d < lim][(r+d)%D] %= MOD

print((dp[-1][0][0] + dp[-1][1][0] - 1) % MOD)

### FIXED CODE ###

K = input()
D = int(input())
L = len(K)
MOD = 10**9+7
dp = [[[0]*D for j in range(2)] for i in range(L+1)] #dp[i][less][modD]
dp[0][0][0] = 1
for i,c in enumerate(K):
    for less in range(2):
        lim = 9 if less else int(c)
        for r in range(D):
            for d in range(lim+1):
                dp[i+1][less or d < lim][(r+d)%D] += dp[i][less][r]
                dp[i+1][less or d < lim][(r+d)%D] %= MOD

print((dp[-1][0][0] + dp[-1][1][0] - 1) % MOD)
### BUGGY CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))
Q = [ ((i*(i+1))/2)/i for i in p]
ans = 0

for i in range(N-K+1):
    ans = max(ans,sum(Q[i:i+K]))
print(ans)


### FIXED CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))
ans = sum(p[:K])
tmp = ans
for i in range(K,N):
    tmp += p[i]-p[i-K]
    ans = max(ans,tmp)
print((ans+K)/2)
### BUGGY CODE ###

import sys
readline = sys.stdin.buffer.readline
from collections import deque
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    H, W, K = map(int, readline().split())
    # いつものパターンと問題文のi,jが逆なので、
    # 問題文のxを変数yに、問題文のyを変数xに代入している
    sy, sx, gy, gx = map(int, readline().split())
    lake = [['@' for _ in range(W+2)]]

    for _ in range(H):
        c = ['@'] + list(readline().decode('utf-8').strip()) + ['@']
        lake.append(c)
    lake.append(['@' for _ in range(W+2)])

    dist = [[INF] * (W+2) for _ in range(H+2)]
    dx = (1, 0, -1, 0)
    dy = (0, 1, 0, -1)
    Q = deque()
    Q.append((sy, sx, 0))
    dist[sy][sx] = 0
    while Q:
        y,x,d = Q.popleft()
        if y == gy and x == gx:
            print(dist[y][x])
            sys.exit()
        for i in range(4):
            for k in range(1,K+1):
                n_y = y + dy[i] * k
                n_x = x + dx[i] * k

                if lake[n_y][n_x] == '.':
                    if dist[n_y][n_x] > d+1:
                        dist[n_y][n_x] = d + 1
                        Q.append((n_y,n_x,d+1))
                    else:
                        continue

                else:
                    break
    print('-1')

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from collections import deque
 
H, W, K = map(int,readline().split())
x1, y1, x2, y2 = map(int,readline().split())
x1 -= 1; y1 -= 1; x2 -= 1; y2 -= 1
C = read().split()

dist = [[-1]*W for i in range(H)]
dist[x1][y1] = 0
d = deque([[x1, y1]])
dxy= [[1, 0], [0, 1], [-1, 0], [0, -1]]
while d:
  x, y = d.popleft()
  if (x, y) == (x2, y2):
    print(dist[x][y])
    quit()
  for dx, dy in dxy:
    xx = x; yy = y
    for i in range(K):
      xx += dx; yy += dy
      if 0<=xx<H and 0<=yy<W and C[xx][yy]!='@':
        if 0 <= dist[xx][yy] <= dist[x][y]:
          break
        if dist[xx][yy] == -1:
           d.append([xx, yy])
        dist[xx][yy] = dist[x][y] + 1
      else:
        break

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

from collections import deque
import sys
sys.setrecursionlimit(300000)

N,M = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
  l,r,d = map(int, input().split())
  l,r = l-1,r-1
  E[l].append((r,d))
  E[r].append((l,-d)) 
  
#for e in E:
#  print(e)
  
# dfs
visited = [False] * N

INF = 10**16
A = [ INF ] * N

def dfs(now, prev, num):
  visited[now] = True
  if A[now] == INF:
    A[now] = num
  else:
    pass
  for nxt, dis in E[now]:
    if nxt == prev:
      continue
    if A[nxt] < INF and A[nxt] != num + dis:
      # ある点において2通りのnum設定の仕方がある
      print("No")
      exit(0)
    if visited[nxt]:
      continue
    dfs(nxt, now, num + dis)
  return 

for i in range(N):
  if visited[i]:
    continue
  dfs(i,-1,0)
  
print("Yes")

### FIXED CODE ###

from collections import deque
N,M = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
  l,r,d = map(int, input().split())
  l,r = l-1,r-1
  E[l].append((r,d))
  E[r].append((l,-d)) 
  
#for e in E:
#  print(e)
  
# bfs
Q = deque()
visited = [False] * N
willSearch = [False] * N
INF = 10**16
A = [ INF ] * N

for i in range(N):
  if visited[i]:
    continue
  Q.append((i,-1,0))
  while Q:
    now, prev, num = Q.popleft()
    visited[now] = True
    if A[now] == INF:
      A[now] = num
    elif A[now] != num:
      # ある点において2通りのnum設定の仕方がある
      #print(now,prev,num,A[inxt])
      print("No")
      exit(0)
    for nxt, dis in E[now]:
      if nxt == prev:
        continue
      if A[nxt] < INF and A[nxt] != num + dis:
        # ある点において2通りのnum設定の仕方がある
        #print(now,prev,num, nxt,dis, A[nxt])
        print("No")
        exit(0)
      if visited[nxt] or willSearch[nxt]:
        continue
      Q.append((nxt, now, num + dis))
      willSearch[nxt] = True
    
print("Yes")
### BUGGY CODE ###

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

cnt = 0
while True:
  n //= k
  cnt += 1
  if n == k:
    cnt += 2
    break
    
print(cnt)
  

### FIXED CODE ###

n, k = map(int, input().split())
cnt = 0
while n >= k:
  n //= k
  cnt += 1
    
print(cnt + 1)
### BUGGY CODE ###

n, m = list(map(int, input().split()))
graph = [float("INF") for i in range(n)]
graph[0] = 0
edge = [tuple(map(int, input().split())) for i in range(m)]
for i in range(2*n):
  flag = False
  for e in edge:
    a, b, c = e
    a, b, c = a-1, b-1, -c
    if graph[b] > graph[a]+c:
      if b==n-1:
        flag = True
      graph[b] = graph[a]+c
if flag:
  print("inf")
else:
  print(-graph[n-1])

### FIXED CODE ###

n, m = list(map(int, input().split()))
graph = [float("INF") for i in range(n)]
graph[0] = 0
edge = [tuple(map(int, input().split())) for i in range(m)]
for i in range(2*n):
  flag = False
  for e in edge:
    a, b, c = e
    a, b, c = a-1, b-1, -c
    if graph[b] > graph[a]+c:
      if b==n-1:
        flag = True
      graph[b] = graph[a]+c
if flag:
  print("inf")
else:
  print(-graph[n-1])
### BUGGY CODE ###

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

ans = [0 for i in range(1000)]
for i in range(N):
    a = S[i]
    for j in range(i+1,N):
        b = S[j]
        for c in '0123456789':
            if c in S[j+1:]:
                s = a + b + c
                ans[int(s)] = 1
print(sum(ans))

### FIXED CODE ###

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

def judge(A,B,C):
    s = S
    a = s.find(A)
    if a < 0:
        return False

    s = s[a+1:]
    b = s.find(B)
    if b < 0:
        return False

    s = s[b+1:]
    c = s.find(C)
    if c < 0:
        return False
    return True

l = '0123456789'
print(sum([int(bool(judge(a,b,c))) for a in l for b in l for c in l]))
### BUGGY CODE ###

from heapq import heappop, heappush, heappushpop

n = int(input())
q = [tuple(int(x) for x in input().split()) for _ in range(n)]

L = []
R = []
a = 1
b = q[0][2]

heappush(L, -q[0][1])

for i in range(1, n):
    #print([L, R])
    temp = q[i]
    if temp[0] == 1:
        a += 1
        if a % 2 == 0:
            p = heappushpop(L, - temp[1])
            heappush(R, - p)
        else:
            p = heappushpop(R, temp[1])
            heappush(L, - p)
        b += temp[2]
    else:
        m = - L[0]
        ans = b
        for x in L:
            ans += abs(m + x)
        for x in R:
            ans += abs(m - x)
        print(m, ans)

### FIXED CODE ###

from heapq import heappop, heappush, heappushpop

n = int(input())
q = [tuple(int(x) for x in input().split()) for _ in range(n)]

L = []
R = []
a = 1
b = q[0][2]

ans = 0

heappush(L, -q[0][1])

for i in range(1, n):
    temp = q[i]
    if temp[0] == 1:
        a += 1
        if a % 2 == 0:
            ans += abs(temp[1] + L[0])
            p = heappushpop(L, - temp[1])
            heappush(R, - p)
        else:
            ans += abs(temp[1] + L[0])
            tl = L[0]
            p = heappushpop(R, temp[1])
            heappush(L, - p)
            if tl != L[0]:
                ans -= abs(tl - L[0])
        b += temp[2]
    else:
        m = - L[0]
        print(m, ans + b)