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

K = input()

#すべての組合せをリスト化する
abc_list = []
for a in range(1, int(K)+1):
  for b in range(1, int(K)+1):
    for c in range(1, int(K)+1):
      abc_list.append([a, b, c])

#ユーグリッド互除法（再起）
def gcd(p, q):
  # ユーグリッド互除法
  if (p%q==0):
    return q
  else:
    return gcd(q, p%q)

# 回答
ans = 0
for lis in abc_list:
  a = lis[0]
  b = lis[1]
  c = lis[2]

  gcd_ab = gcd(a, b)
  gcd_abc = gcd(gcd_ab, c)

  ans += gcd_abc

print(ans)

### FIXED CODE ###

import itertools
K = int(input())

#ユーグリッド互除法（再起）
def gcd(p, q):
  # ユーグリッド互除法
  if (p%q==0):
    return q
  else:
    return gcd(q, p%q)

ans = 0

for abc in itertools.combinations_with_replacement([i+1 for i in range(K)], 3):
  a,b,c = abc
  gcd_ab = gcd(a, b)
  gcd_abc = gcd(gcd_ab, c)

  # 組み合わせ数を補整する
  if a == b == c:
    ans += gcd_abc
  elif a==b or b==c or a==c:
    ans += gcd_abc*3
  else:
    ans += gcd_abc * 6

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

import itertools

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

c = list(itertools.combinations(l, 2))

sum=0
for i in range(len(c)):
    sum+=c[i][0]*c[i][1]

print(sum%(10**9+7))

### FIXED CODE ###

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

sum=0
f=0

for i in range(n-1):
    f=f+a[i]
    sum+=f*a[i+1]

print(sum%(10**9+7))
### BUGGY CODE ###

import sys
from sys import stdin
input = stdin.readline
N=int(input())
edges=[list(map(int,input().split())) for i in range(N)]
ans=0
for k in range(N):
  for i in range(N):
    for j in range(i):
      if edges[i][j]>edges[i][k]+edges[k][j]:
        print(-1)
        sys.exit()
      if k==0:
        need=1
        for l in range(N):
          if l!=i and l!=j and edges[i][j]==edges[i][l]+edges[l][j]:
            need=0
            break
        if need:ans+=edges[i][j]
        
print(ans)

### FIXED CODE ###

def Warshall_Floyd(edges,N):
  """頂点N個のグラフ上の隣接行列edges(空欄はinfとせよ)が与えられたとき, 
  2点間の最短距離距離を隣接行列で返す"""
  for k, i, j in itertools.product(range(N), range(N),range(N)):
    if edges[i][j]>edges[i][k]+edges[k][j]: return 1
  return 0
 
import sys
import itertools
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
if Warshall_Floyd(A,N):
  print(-1)
  sys.exit()
 
ans=0
for i, j in itertools.product(range(N),range(N)):
  need=1
  for k in range(N):
    if k!=i and k!=j and A[i][j]==A[i][k]+A[k][j]:
      need=0
      break
  if need:ans+=A[i][j]
print(ans//2)
### BUGGY CODE ###

h,w=map(int,input().split())
sl=[input() for i in range(h)]
ll=[[0]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        if sl[i][j]=='.':
            if j==0:
                ll[i][j]=1
            else:
                ll[i][j]=ll[i][j-1]+1
        else:
            ll[i][j]=0
rl=[[0]*w for i in range(h)]
for i in range(h):
    for j in range(w-1,-1,-1):
        if sl[i][j]=='.':
            if j==w-1:
                rl[i][j]=1
            else:
                rl[i][j]=rl[i][j+1]+1
        else:
            rl[i][j]=0
ul=[[0]*w for i in range(h)]
for j in range(w):
    for i in range(h):
        if sl[i][j]=='.':
            if i==0:
                ul[i][j]=1
            else:
                ul[i][j]=ul[i-1][j]+1
        else:
            ul[i][j]=0
dl=[[0]*w for i in range(h)]
for j in range(w):
    for i in range(h-1,-1,-1):
        if sl[i][j]=='.':
            if i==h-1:
                dl[i][j]=1
            else:
                dl[i][j]=dl[i+1][j]+1
        else:
            dl[i][j]=0
ans=0
for i in range(h):
    for j in range(w):
            ans=max(ans,ll[i][j]+rl[i][j]+ul[i][j]+dl[i][j]-3)
print(ans)

### FIXED CODE ###

h,w=map(int,input().split())
sl=[input() for i in range(h)]
ll=[[0]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        if sl[i][j]=='.':
            if j==0:
                ll[i][j]=1
            else:
                ll[i][j]=ll[i][j-1]+1
        else:
            ll[i][j]=0
rl=[[0]*w for i in range(h)]
for i in range(h):
    for j in range(w-1,-1,-1):
        if sl[i][j]=='.':
            if j==w-1:
                rl[i][j]=1
            else:
                rl[i][j]=rl[i][j+1]+1
        else:
            rl[i][j]=0
ul=[[0]*w for i in range(h)]
for j in range(w):
    for i in range(h):
        if sl[i][j]=='.':
            if i==0:
                ul[i][j]=1
            else:
                ul[i][j]=ul[i-1][j]+1
        else:
            ul[i][j]=0
dl=[[0]*w for i in range(h)]
for j in range(w):
    for i in range(h-1,-1,-1):
        if sl[i][j]=='.':
            if i==h-1:
                dl[i][j]=1
            else:
                dl[i][j]=dl[i+1][j]+1
        else:
            dl[i][j]=0
ans=0
for i in range(h):
    for j in range(w):
            ans=max(ans,ll[i][j]+rl[i][j]+ul[i][j]+dl[i][j]-3)
print(ans)
### BUGGY CODE ###

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

a = []
while True:
    n = abs(n - k)
    a.append(n)
    if n < k // 2:
        break
    
print(min(a))


### FIXED CODE ###

n, k = map(int, input().split())
s = n % k
s2 = k - s
print(min(s, s2))
### BUGGY CODE ###

import collections

n = int(input())
al = [int(i) for i in input().split()]
q = int(input())

counter = collections.Counter(al)

for _ in range(q):
  b, c = [int(i) for i in input().split()]
  count = counter[b]
  counter[b] = 0
  counter[c] += count
  total = 0
  for (v, c) in counter.most_common():
    total += v * c
  print(total)

### FIXED CODE ###

import collections

n = int(input())
al = [int(i) for i in input().split()]
q = int(input())

counter = collections.Counter(al)

total = 0
for (v, c) in counter.most_common():
  total += v * c
for _ in range(q):
  b, c = [int(i) for i in input().split()]
  count = counter[b]
  counter[b] = 0
  counter[c] += count
  total = total + (c - b) * count
  print(total)
### BUGGY CODE ###

import itertools
N = int(input())
points = list(map(int, input().split()))
ans = 0

for k in range(max(points)+1):
    arc_list = []
    abc_list = []
    for point in points:
        if point >= k:
            arc_list.append(point)
        else:
            abc_list.append(point)
    if len(arc_list) == len(abc_list):
        ans += 1

print(ans)

### FIXED CODE ###

import itertools
import numpy as np

N = int(input())
points = np.array(list(map(int, input().split())))
ans = 0
s_points = sorted(points)

ans = s_points[int(N/2)] - s_points[int(N/2)-1]

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

n = int(input())
la = list(map(int, input().split()))
import functools
import operator

ans = functools.reduce(operator.mul, la)
if ans > 10**18:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default
      
n = int(input())
la = list(map(int, input().split()))
import sys
if my_index(la, 0) > 0:
  print(0)
  sys.exit()

ans = 1
for i in la:
  ans *= i
  if ans > 10**18:
    print(-1)
    sys.exit()
print(ans)
### BUGGY CODE ###

N, M = [int(i) for i in input().split()]
XS = [int(i) for i in input().split()]

if M < N:
  print(0)
else:
  xs = sorted(XS)
  ds = list(map(lambda a,b: b-a, xs, xs[1:]))
  for _ in range(N-1):
    ds.remove(max(ds))

  print(sum(ds))


### FIXED CODE ###

N, M = [int(i) for i in input().split()]
XS = [int(i) for i in input().split()]

if M <= N:
  print(0)
else:
  xs = sorted(XS)
  ds = list(map(lambda a,b: b-a, xs, xs[1:]))
  print(sum(sorted(ds)[:M-N]))
### BUGGY CODE ###

def main():
    from itertools import product

    n, s = int(input()), input()
    ans = 0
    for i in range(n - 2):
        for j in range(i + 1, n - 1):
            for k in range(j + 1, n):
                f = s[i] != s[j] and s[j] != s[k] and s[k] != s[i]
                g = (j - i) != (k - j)
                if f and g:
                    ans += 1
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n, s = int(input()), input()
    r, g, b = s.count('R'), s.count('G'), s.count('B')
    ans = r * g * b
    v = {'R', 'G', 'B'}
    for i in range(n - 2):
        for j in range(n // 2 + 1):
            if i + j + j < n:
                if v == {s[i], s[i + j], s[i + j + j]}:
                    ans -= 1
    print(ans)


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

N = int(input())
S = [''] * N
for i in range(N):
  S[i] = input()
cnt = 0
for a in range(N):
  for i in range(N):
    _i = (i - a) % N
    for j in range(i):
      if S[_i][j] != S[(j - a) % N][i]:
        break
    else:
      continue
    break
  else:
    cnt += N
print(cnt)

### FIXED CODE ###

N = int(input())
S = [''] * N
for i in range(N):
  S[i] = input()
cnt = 0
for a in range(N):
  for i in range(N):
    _i = (i - a) % N
    for j in range(i):
      if S[_i][j] != S[(j - a) % N][i]:
        break
    else:
      continue
    break
  else:
    cnt += N
print(cnt)
### BUGGY CODE ###

from copy import deepcopy
N = int(input())
A = list(map(int,input().split()))
count = 0
for i,a in enumerate(A):
    flag = 0
    A2 = deepcopy(A)
    del A2[i]
    Aas = sorted(A2)
    if a not in A2:
        for b in Aas:
            if a % b  == 0:
                flag = 1
                break
            if a/b < 2:
                break
    else:
        flag = 1
    if flag == 0:
        count += 1
print(count)


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
M = 1000001
cnt = [0]*M
ans = 0
for x in A:
    if cnt[x] != 0:
        cnt[x] = 2
        continue
    for i in range(x,M,x):
        cnt[i] += 1
for x in A:
    if cnt[x] == 1:
        ans += 1
print(ans)
### BUGGY CODE ###

S=list(input())
N=len(S)
s=reversed(S)
X=[0]*N
for i in range(N):
    m=1
    if S[i]=="R":
        while 1:
            if S[i]!=S[i+m]:
                break
            m+=1
        if m%2==0:
            X[i+m]+=1
        else:
            X[i+m-1]+=1
    else:
        while 1:
            if S[i]!=S[i-m]:
                break
            m+=1
        if m%2==0:
            X[i-m]+=1
        else:
            X[i-m+1]+=1
for i in range(N):
    print(X[i])
        
        


### FIXED CODE ###

S=list(input())
N=len(S)
s=reversed(S)
X=[0]*N
for i in range(N):
    m=1
    if i>0 and S[i]=="R" and S[i]==S[i-1]:
        m=k-1
        if m%2==0:
            X[i+m]+=1
        else:
            X[i+m-1]+=1
    else:

        if S[i]=="R":
            while 1:
                if S[i]!=S[i+m]:
                    break
                m+=1
            if m%2==0:
                X[i+m]+=1
            else:
                X[i+m-1]+=1
    if i>0 and S[i]=="L" and S[i]==S[i-1]:
        m=k+1
        if m%2==0:
            X[i-m]+=1
        else:
            X[i-m+1]+=1
    else:
        if S[i]=="L":
            while 1:
                if S[i]!=S[i-m]:
                    break
                m+=1
            if m%2==0:
                X[i-m]+=1
            else:
                X[i-m+1]+=1
    k=m
for i in range(N):
    print(X[i])
### BUGGY CODE ###

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

for i in range(0,n):
  aa=a.count(i+1)
  print (aa)

### FIXED CODE ###

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

#for i in range(0,n):
#  print (a.count(i+1))
#  a= [a[j] for j in range(0, len(a)) if a[j] != i+1]
#
#  print (a)

kekka= [0] * (n+1)
for i in range(0,n-1):
  kekka[a[i]]+=1

for i in range(1,n+1):
  print (kekka[i])
### BUGGY CODE ###

mod = 10 ** 9 + 7
N = int(input())
A = list(map(lambda x: int(x) % mod, input().split(" ")))

ans = sum((A[i] % mod) * (A[j] % mod) for i in range(0,N-1) for j in range(i+1,N))

print(ans % mod)


### FIXED CODE ###

mod = 1000000007
N = int(input())
A = list(map(lambda x: int(x) % mod, input().split(" ")))

"""
累積話を計算しておく: O(N)
"""
_sum = 0
for i in range(N):
    _sum += A[i]
    _sum %= mod

"""
1重ループ内で下記を行う: O(N)

- 端のブロックを累積和から崩す（減算）
- 端のブロックと累積和をかける
- modをとる
"""
ans = 0
for i in range(N):
    # 累積和の端のブロックを崩す
    _sum -= A[i]

    ans += A[i] * _sum
    ans %= mod

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

n,d,a = map(int,input().split())
l = [list(map(int,input().split())) for i in range(n)]
l.sort()
count = 0
import math
i = 0
while i < n:
    sn = i
    s = l[i][0]
    mi = math.ceil(l[i][1]/a)
    count += mi
    
    while i < n and l[i][0] <= s+2*d:
        
        l[i][1] -= mi*a
        i += 1
        
    for j in range(sn,i+1):
        if j >= n:
            print(count)
            exit()
        if l[j][1] > 0:
            i = j
            
            break

print(count)   


### FIXED CODE ###

def main():
    n,d,a = map(int,input().split())
    l = [list(map(int,input().split())) for i in range(n)]
    l.sort()
    count = 0
    from collections import deque

    i = 0
    area = deque([])
    damage = deque([])
    total_damage = 0
    count = 0
    ans = 0
    for pos,hp in l:
        while area:
            ar = area[0]
            if ar < pos:
                area.popleft()
                power = damage.popleft()
                total_damage -= power
            else:
                break
        if hp <= total_damage:
            continue
        else:
            count = (hp-total_damage+a-1)//a
            ans += count
            total_damage += count*a
            area.append(pos+2*d)
            damage.append(count*a)

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

def resolve():
    N, W = list(map(int, input().split()))
    WV = [[0, 0]]+[list(map(int, input().split())) for _ in range(N)]
    dp = [[0 for _ in range(W+1)] for ___ in range(N+1)]
    
    for i in range(1, N+1):
        for j in range(W+1):
            w, v = WV[i]
            if j >= w:
                dp[i][j] = max(dp[i-1][j-w] + v, dp[i-1][j])
            else:
                dp[i][j] = dp[i-1][j]
    print(dp[N][W])


if __name__ == '__main__':
    resolve()

### FIXED CODE ###

def resolve():
    N, W = list(map(int, input().split()))
    WV = [list(map(int, input().split())) for _ in range(N)]
    wbase = WV[0][0]
    d = {
        wbase: [0],
        wbase+1: [0],
        wbase+2: [0],
        wbase+3: [0],
    }
    for w, v in WV:
        d[w].append(v)
    for v in d.values():
        v.sort(reverse=True)
    
    accs = {}
    for i in range(4):
        accs[wbase+i] = [0]
        for j in range(len(d[wbase+i])):
            accs[wbase+i].append(accs[wbase+i][j]+d[wbase+i][j])
    
    res = 0
    for i in range(len(d[wbase])):
        for j in range(len(d[wbase+1])):
            for k in range(len(d[wbase+2])):
                for l in range(len(d[wbase+3])):
                    if i*wbase+j*(wbase+1)+k*(wbase+2)+l*(wbase+3) <= W:
                        res = max(res, accs[wbase][i]+accs[wbase+1][j]+accs[wbase+2][k]+accs[wbase+3][l])
    print(res)


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

from sys import stdin
import numpy as np

N, M = [int(x) for x in stdin.readline().split()]
A = np.array([int(a) for a in stdin.readline().split()], dtype=np.int64)

cumsum_remainders = (np.hstack([0, A]) % M).cumsum() % M

total = 0
for remainder in np.unique(cumsum_remainders):
    count = (cumsum_remainders == remainder).sum()
    total += count * (count - 1) // 2
print(total)


### FIXED CODE ###

from sys import stdin
from collections import Counter
import numpy as np

N, M = [int(x) for x in stdin.readline().split()]
A = np.array([int(a) for a in stdin.readline().split()], dtype=np.int64)

cum_remainders = (np.hstack([0, A]) % M).cumsum() % M

remainder_counts = Counter(cum_remainders)
combinations = 0
for count in remainder_counts.values():
    combinations += count * (count - 1) // 2
print(combinations)
### BUGGY CODE ###

from collections import deque
n=int(raw_input())
r=[map(int,raw_input().split()) for _ in xrange(n)]
m=int(raw_input())
pa=[map(int,raw_input().split()) for _ in xrange(m)]
for i in xrange(m):
    d=[1]*n
    q=deque([pa[i][0]])
    used=[False]*n
    used[pa[i][0]-1]=True
    while len(q)!=0:
        f=0
        p=q.popleft()
        p-=1
        if d[p]==pa[i][2]:break
        for j in r[p][2:]:
            j-=1
            if pa[i][1]-1==j:
                f=1
                d[j]+=d[p]
                break
            if used[r[j][0]-1]:continue
            q.append(j+1)
            d[j]=d[p]+1
            used[j]=True
        if f==1:
            break
    if f==1:
        print(d[j])
    else:
        print("NA")

### FIXED CODE ###

n=int(raw_input())
g=[[1000000]*n for _ in xrange(n)]
for i in xrange(n):
    g[i][i]=0
for i in xrange(n):
    r=map(int,raw_input().split())
    for j in r[2:]:
        g[r[0]-1][j-1]=1
for k in xrange(n):
    for i in xrange(n):
        for j in xrange(n):
            g[i][j]=min(g[i][j],g[i][k]+g[k][j])
m=int(raw_input())
for i in xrange(m):
    s,d,v=map(int,raw_input().split())
    s-=1
    d-=1
    if g[s][d]<v:
        print(g[s][d]+1)
    else:
        print('NA')
### BUGGY CODE ###


import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7

from fractions import gcd
from functools import reduce

L = A[0]
for i in range(1,N):
  L=(L*A[i])//gcd(L,A[i])

ans = 0

for i in range(N):
  ans += (L // A[i]) % mod

print(ans % mod)


### FIXED CODE ###


N = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7

from fractions import gcd

L = A[0]
for i in range(1,N):
  L=(L*A[i])//gcd(L,A[i])

ans = 0

for i in range(N):
  ans += (L // A[i])

print(ans % mod)
### BUGGY CODE ###

from itertools import combinations
import numpy as np

n=int(input())
l=sorted([int(i) for i in input().split()])

v=np.array([l[0], l[1]])
vsum=np.array([l[0]+l[1]])

c=0

for i in range(2, n):
    p=l[i]
    c+=np.sum(vsum>p)
    vsum = np.concatenate([vsum, v+p], 0)
    v=np.append(v, p)

print(c)

### FIXED CODE ###

from bisect import bisect_left
N = int(input())
L = sorted([int(i) for i in input().split()])

res = 0

for i in range(N):
    for j in range(i+1, N):
        r = bisect_left(L, L[i]+L[j])
        res += max(r-(j+1), 0)

print(res)
### BUGGY CODE ###

N,W=map(int,input().split())
w=[]
v=[]
for i in range(N):
    a,b=map(int,input().split())
    w.append(a)
    v.append(b)
dp=[[0 for i in range(W+1)] for j in range(N+1)]
for i in range(N):
    for j in range(W+1):
        if j>=w[i]:
            dp[i+1][j]=max(dp[i][j-w[i]]+v[i],dp[i][j])
        else:
            dp[i+1][j]=dp[i][j]
print(dp[N][W])


### FIXED CODE ###

N,W=map(int,input().split())
taple=[]
for i in range(N):
    w,v=map(int,input().split())
    taple.append((w,v))
dp=[[10**22]*(N*(10**3)+1) for i in range(N+1)]
dp[0][0]=0
for i in range(1,N+1):
    w,v=taple[i-1]
    for j in range(N*(10**3)+1):
        if j>=v:
            dp[i][j]=min(dp[i-1][j-v]+w,dp[i-1][j])
        else:
            dp[i][j]=dp[i-1][j]
for i in range(N*(10**3),-1,-1):
    if dp[N][i]<=W:
        print(i)
        break
### BUGGY CODE ###

N,M,Q= list(map(int, input().split()))
LR = [list(map(int, input().split())) for _ in range(M)]
PQ = [list(map(int, input().split())) for _ in range(Q)]

from itertools import product, permutations, combinations

memo = {(i,i):0 for i in range(1, N+1)}
trains = {(i,i):0 for i in range(1, N+1)}
for x in combinations(range(1,N+1), 2):
  x = (min(x), max(x))
  memo[x] = 0
  trains[x] = 0

for l, r in LR:
  memo[(l,r)] +=1

for k, v in memo.items():
  for l, r in product(range(1,k[0]+1), range(k[1], N+1)):
    trains[(l,r)] += v

for p,q in PQ:
  print(trains[(p,q)])

### FIXED CODE ###

N,M,Q= list(map(int, input().split()))
LR = [list(map(int, input().split())) for _ in range(M)]
PQ = [list(map(int, input().split())) for _ in range(Q)]

import numpy as np

trains = np.array([[0]*N for _ in range(N)])

for l, r in LR:
  trains[l-1][r-1] +=1

# 二次元累積和
row_sum = trains.cumsum(axis=1)
matrix_sum = row_sum.cumsum(axis=0)

for p,q in PQ:
  if p==1:
    print(matrix_sum[q-1, q-1])
  else:
    print(matrix_sum[q-1,q-1] - matrix_sum[p-2,q-1])
### BUGGY CODE ###

# DPの計算量…DPテーブルのノードの数＋エッジの数
# https://atcoder.jp/contests/dp/tasks/dp_b
# 理屈はあってるが、PythonなのでTLEになります…
import numpy as np


def chmin(a, b):
    '''a>bならbを代入して返すメソッド'''
    if a > b:
        a = b
        return a
    else:
        return a


def main():
    '''もらうDPとして実装'''
    N, K = list(map(int, input().split()))
    H = list(map(int, input().split()))
    # 最小なものにコストを書き換えたいので初期値は大きく取る
    dp = np.ones(N) * 10000000

    # 最初はコスト０
    dp[0] = 0
    for i in range(1, N):
        dp[i] = min(dp[i - j] + abs(H[i] - H[i - j]) for j in range(1, min(i + 1, K + 1)))
    print(int(dp[i]))


main()


### FIXED CODE ###

def test():
    N, K = map(int, input().split())
    H = list(map(int, input().split()))
    dp = [float('inf')]*N
    dp[0] = 0
 
    for i in range(1, N):
        dp[i] = min(dp[j] + abs(H[i] - H[j]) for j in range(max(i-K, 0), i))
 
    print(dp[-1])
 
if __name__ == '__main__':
    test()
### BUGGY CODE ###

q = int(input())
a = []
ai = 0
bs = 0
for i in range(q):
    ipt = list(map(int,input().split()))
    if ipt[0] == 1:
        a.append(ipt[1])
        bs += ipt[2]
        ai += 1
    else:
        a.sort()
        an = a[(ai-1)//2]
        bn = bs
        for j in a:
            bn += abs(j-an)
        print(an,bn)


### FIXED CODE ###

import heapq
q = int(input())
l = []
r = []
ai = 0
bs = 0
for i in range(q):
    ipt = list(map(int,input().split()))
    if ipt[0] == 1:
        al = heapq.heappushpop(l,-ipt[1])
        ar = heapq.heappushpop(r,ipt[1])
        ai -= (al+ar)
        heapq.heappush(l,-ar)
        heapq.heappush(r,-al)
        bs += ipt[2]
    else:
        an = heapq.heappop(l)
        print(-an,bs+ai)
        heapq.heappush(l,an)
### BUGGY CODE ###

import math
 
N=int(input())
count=[0]*(N+1)
for x in range(1,N+1):
  for y in range(1,N+1):
    for z in range(1,N+1):
      n=x**2+y**2+z**2+x*y+y*z+z*x
      if(n<=N):
        count[n]+=1
for j in range(1,N+1):
  print(count[j])

### FIXED CODE ###

N=int(input())
count=[0]*(N+1)
for x in range(1,100):
  for y in range(1,100):
    for z in range(1,100):
      n=x*x+y*y+z*z+x*y+y*z+z*x
      if(n<=N):
        count[n]+=1
for i in range(1,N+1):
  print(count[i])
### BUGGY CODE ###

import math
a,b,n = map(int,input().split())
li = []

for x in range(n+1):
    li.append(math.floor((a*(x))/b) - a * math.floor(x/b))
print(max(li))

### FIXED CODE ###

import math
 
A, B, N = map(int, input().split())
 
 
ans1 = 0
 
if N > B - 1:
    x = B-1
    print(int((A * x) / B) - A * int(x / B))
elif N <= B - 1:
    x = N
    print(int((A * x) / B) - A * int(x / B))
### BUGGY CODE ###

import numpy as np

N, M, Q = map(int, input().split())

S = np.empty((N+1, M+1), dtype='int')

for n in range(1, N+1):
    S[n, :] = [0] + list(map(int, list(input())))

# count nodes
N_cum = np.cumsum(np.cumsum(S, axis=0), axis=1) 
# count edges(row)
ER_cum = np.cumsum(np.cumsum(S[:N, :]*S[1:, :], axis=0), axis=1) 
# count edges(col)
EC_cum = np.cumsum(np.cumsum(S[:, :M]*S[:, 1:], axis=0), axis=1) 

sol_list = []

for _ in range(Q):
    x1, y1, x2, y2 = map(int, input().split())
    # nodes
    N_nodes = N_cum[x2, y2] - N_cum[x1-1, y2] - N_cum[x2, y1-1] + N_cum[x1-1, y1-1]
    # edges(row)
    N_edges1 = ER_cum[x2-1, y2] - ER_cum[x1-1, y2] - ER_cum[x2-1, y1-1] + ER_cum[x1-1, y1-1]
    # edges(col)
    N_edges2 = EC_cum[x2, y2-1] - EC_cum[x1-1, y2-1] - EC_cum[x2, y1-1] + EC_cum[x1-1, y1-1]
    
    sol_list.append(N_nodes - N_edges1 - N_edges2)

for q in range(Q):
    print(sol_list[q])

### FIXED CODE ###

import numpy as np

N, M, Q = map(int, input().split())

S = np.zeros((N+1, M+1), dtype='float32')

for n in range(1, N+1):
    S[n, 1:] = list(map(int, list(input())))

# count nodes
N_cum = np.cumsum(np.cumsum(S, axis=0), axis=1) 
# count edges(row)
ER_cum = np.cumsum(np.cumsum(S[:N, :]*S[1:, :], axis=0), axis=1) 
# count edges(col)
EC_cum = np.cumsum(np.cumsum(S[:, :M]*S[:, 1:], axis=0), axis=1) 

sol_list = []

for _ in range(Q):
    x1, y1, x2, y2 = map(int, input().split())
    # nodes
    N_nodes = N_cum[x2, y2] - N_cum[x1-1, y2] - N_cum[x2, y1-1] + N_cum[x1-1, y1-1]
    # edges(row)
    N_edges1 = ER_cum[x2-1, y2] - ER_cum[x1-1, y2] - ER_cum[x2-1, y1-1] + ER_cum[x1-1, y1-1]
    # edges(col)
    N_edges2 = EC_cum[x2, y2-1] - EC_cum[x1-1, y2-1] - EC_cum[x2, y1-1] + EC_cum[x1-1, y1-1]
    
    sol_list.append(N_nodes - N_edges1 - N_edges2)

for q in range(Q):
    print(int(sol_list[q]))