Problem:
 Score : 600 points    Problem Statement There is a function f(x) , which is initially a constant function f(x) = 0 .  We will ask you to process Q queries in order. There are two kinds of queries, update queries and evaluation queries, as follows:   An update query 1 a b : Given two integers a and b , let g(x) = f(x) + |x - a| + b and replace f(x) with g(x) .  An evaluation query 2 : Print x that minimizes f(x) , and the minimum value of f(x) . If there are multiple such values of x , choose the minimum such value.   We can show that the values to be output in an evaluation query are always integers, so we ask you to print those values as integers without decimal points.      Constraints  All values in input are integers.  1 \leq Q \leq 2 \times 10^5  -10^9 \leq a, b \leq 10^9  The first query is an update query.         Input Input is given from Standard Input in the following format:  Q  Query_1  :  Query_Q   See Sample Input 1 for an example.      Output For each evaluation query, print a line containing the response, in the order in which the queries are given.  The response to each evaluation query should be the minimum value of x that minimizes f(x) , and the minimum value of f(x) , in this order, with space in between.        Sample Input 1 4
1 4 2
2
1 1 -8
2      Sample Output 1 4 2
1 -3  In the first evaluation query, f(x) = |x - 4| + 2 , which attains the minimum value of 2 at x = 4 .  In the second evaluation query, f(x) = |x - 1| + |x - 4| - 6 , which attains the minimum value of -3 when 1 \leq x \leq 4 . Among the multiple values of x that minimize f(x) , we ask you to print the minimum, that is, 1 .       Sample Input 2 4
1 -1000000000 1000000000
1 -1000000000 1000000000
1 -1000000000 1000000000
2      Sample Output 2 -1000000000 3000000000

Solution (Python):
import sys
from heapq import heapify,heappop,heappush
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  


ans = 0
left,right = [],[]
heapify(left)
heapify(right)
r = 0

Q = I()
for _ in range(Q):
    q = LI()
    if q[0] == 1:
        a,b = q[1:]
        ans += b
        if r == 0:
            heappush(left,-a)
        elif r == 1:
            x1 = -heappop(left)
            ans += abs(a-x1)
            if x1 < a:
                x1,a = a,x1
            heappush(left,-a)
            heappush(right,x1)
        else:
            x1 = -heappop(left)
            x2 = heappop(right)
            if r % 2 == 0:
                ans += max(0,x1-a,a-x2,0)
                heappush(left,-x1)
                if a <= x2:
                    heappush(left,-a)
                    heappush(right,x2)
                else:
                    heappush(left,-x2)
                    heappush(right,a)
            else:
                ans += abs(x1-a)
                heappush(right,x2)
                if a <= x1:
                    heappush(left,-a)
                    heappush(right,x1)
                else:
                    heappush(left,-x1)
                    heappush(right,a)
        r += 1
    else:
        x = -heappop(left)
        print(x,ans)
        heappush(left,-x)

Solution (Python):
import sys
from heapq import heapify,heappop,heappush
sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  
def LS2(): return list(sys.stdin.readline().rstrip())  


ans = 0
left,right = [],[]
heapify(left)
heapify(right)
r = 0

Q = I()
for _ in range(Q):
    q = LI()
    if q[0] == 1:
        a,b = q[1:]
        ans += b
        if r == 0:
            heappush(left,-a)
        elif r == 1:
            x1 = -heappop(left)
            ans += abs(a-x1)
            if x1 < a:
                x1,a = a,x1
            heappush(left,-a)
            heappush(right,x1)
        else:
            x1 = -heappop(left)
            x2 = heappop(right)
            if r % 2 == 0:
                ans += max(0,x1-a,a-x2,0)
                if a <= x2:
                    heappush(left,-x1)
                    heappush(left,-a)
                    heappush(right,x2)
                else:
                    heappush(left,-x1)
                    heappush(left,-x2)
                    heappush(right,a)
            else:
                ans += abs(x1-a)
                if a <= x1:
                    heappush(left,-a)
                    heappush(right,x1)
                    heappush(right,x2)
                else:
                    heappush(left,-x1)
                    heappush(right,a)
                    heappush(right,x2)
        r += 1
    else:
        x = -heappop(left)
        print(x,ans)
        heappush(left,-x)

Solution (Python):
import heapq
Q = int(input())
ans = 0
L = []
R = []
for _ in range(Q):
    q = input()
    if q[0] == '1':
        _, a, b = map(int, q.split())
        ans += b
        if len(L) > 0 and not -L[0] <= a <= R[0]:
            ans += min(abs(a + L[0]), abs(a - R[0]))
        l = heapq.heappushpop(L, -a)
        r = heapq.heappushpop(R, a)
        heapq.heappush(L, -r)
        heapq.heappush(R, -l)
    else:
        print(-L[0], ans)

Solution (Python):
import sys
from heapq import heappush, heappop

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    Q = int(readline())

    hi = []
    lo = []
    hi_sum = lo_sum = 0
    b_sum = 0

    ans = []
    for _ in range(Q):
        A = list(map(int, readline().split()))
        if len(A) == 3:
            a, b = A[1], A[2]
            b_sum += b

            if not lo:
                lo.append(-a)
                lo_sum += a
            else:
                vec = [a]
                vec.append(-heappop(lo))
                lo_sum -= vec[1]
                if hi:
                    vec.append(heappop(hi))
                    hi_sum -= vec[2]
                    
                vec.sort()
                
                if len(vec) == 2:
                    heappush(lo, -vec[0])
                    heappush(hi, vec[1])
                    lo_sum += vec[0]
                    hi_sum += vec[1]
                elif len(lo) > len(hi):
                    heappush(lo, -vec[0])
                    heappush(hi, vec[1])
                    heappush(hi, vec[2])
                    lo_sum += vec[0]
                    hi_sum += vec[1]
                    hi_sum += vec[2]
                else:
                    heappush(lo, -vec[0])
                    heappush(lo, -vec[1])
                    heappush(hi, vec[2])
                    lo_sum += vec[0]
                    lo_sum += vec[1]
                    hi_sum += vec[2]
        else:
            x = -lo[0]
            val = x * (len(lo) - len(hi)) - lo_sum + hi_sum + b_sum
            ans.append((x, val))

    for x, val in ans:
        print(x, val)

    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from heapq import heappush, heappop

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    Q = int(readline())

    hi = []
    lo = []
    hi_sum = lo_sum = 0
    b_sum = 0

    ans = []
    for _ in range(Q):
        A = list(map(int, readline().split()))
        if len(A) == 3:
            a, b = A[1], A[2]
            b_sum += b

            if not lo:
                lo.append(-a)
                lo_sum += a
            else:
                if a <= -lo[0]:
                    heappush(lo, -a)
                    lo_sum += a
                else:
                    heappush(hi, a)
                    hi_sum += a

            if len(hi) > len(lo):
                x = heappop(hi)
                hi_sum -= x
                heappush(lo, -x)
                lo_sum += x
            elif len(hi) + 1 < len(lo):
                x = -heappop(lo)
                lo_sum -= x
                heappush(hi, x)
                hi_sum += x
        else:
            x = -lo[0]
            val = x * (len(lo) - len(hi)) - lo_sum + hi_sum + b_sum
            ans.append((x, val))

    for x, val in ans:
        print(x, val)

    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from heapq import heappush, heappop

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    Q = int(readline())

    hi = []
    lo = []
    hi_sum = lo_sum = 0
    b_sum = 0

    ans = []
    for _ in range(Q):
        A = list(map(int, readline().split()))
        if len(A) == 3:
            a, b = A[1], A[2]
            b_sum += b

            if not lo:
                lo.append(-a)
                lo_sum += a
            else:
                if a <= -lo[0]:
                    heappush(lo, -a)
                    lo_sum += a
                else:
                    heappush(hi, a)
                    hi_sum += a

            if len(hi) > len(lo):
                x = heappop(hi)
                hi_sum -= x
                heappush(lo, -x)
                lo_sum += x
            elif len(hi) + 1 < len(lo):
                x = -heappop(lo)
                lo_sum -= x
                heappush(hi, x)
                hi_sum += x
        else:
            x = -lo[0]
            val = x * (len(lo) - 1) - (lo_sum - x) + hi_sum - x * len(hi) + b_sum
            ans.append((x, val))

    for x, val in ans:
        print(x, val)

    return


if __name__ == '__main__':
    main()

Solution (Python):
import heapq
const = 0
left = []
right = []

q = int(input())
cnt = 0
left_sum = 0
right_sum = 0
for _ in range(q):
    t = list(map(int, input().split()))
    if t[0] == 1:
        
        a, b = t[1:]
        const += b
        if cnt % 2 == 0:
            if not right:
                heapq.heappush(left, -a)
                left_sum += a
                cnt += 1
                
                continue

            c = heapq.heappop(right)
            right_sum -= c
            if a <= c:
                heapq.heappush(left, -a)
                heapq.heappush(right, c)
                left_sum += a
                right_sum += c
            else:
                heapq.heappush(left, -c)
                heapq.heappush(right, a)
                left_sum += c
                right_sum += a
        else:
            c = heapq.heappop(left)
            left_sum += c
            if a <= -c:
                heapq.heappush(left, -a)
                heapq.heappush(right, -c)
                left_sum += a
                right_sum -= c
            else:
                heapq.heappush(left, c)
                heapq.heappush(right, a)
                left_sum -= c
                right_sum += a
        cnt += 1
        
    else:
        tmp = -left[0]
        print(tmp, const - left_sum + right_sum + tmp * (cnt % 2))

Solution (Python):
import heapq
const = 0
left = []
right = []

q = int(input())
cnt = 0
left_sum = 0
right_sum = 0
for _ in range(q):
    t = list(map(int, input().split()))
    if t[0] == 1:
        
        a, b = t[1:]
        const += b
        if cnt % 2 == 0:
            if not right:
                heapq.heappush(left, -a)
                left_sum += a
                cnt += 1
                
                continue

            c = heapq.heappop(right)
            right_sum -= c
            if a <= c:
                heapq.heappush(left, -a)
                heapq.heappush(right, c)
                left_sum += a
                right_sum += c
            else:
                heapq.heappush(left, -c)
                heapq.heappush(right, a)
                left_sum += c
                right_sum += a
        else:
            c = heapq.heappop(left)
            left_sum += c
            if a <= -c:
                heapq.heappush(left, -a)
                heapq.heappush(right, -c)
                left_sum += a
                right_sum -= c
            else:
                heapq.heappush(left, c)
                heapq.heappush(right, a)
                left_sum -= c
                right_sum += a
        cnt += 1
        
    else:
        tmp = -left[0]
        print(tmp, const - left_sum + right_sum + tmp * (cnt % 2))

Solution (Python):
import sys
input = sys.stdin.readline

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
  
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
  
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

def print_bit(B):
    n = B.size
    ANS = []
    for i in range(n):
        ANS.append(B.sum(i+1) - B.sum(i))
    print(*ANS)


l = 10000
ll = 100
q = int(input())
Q = [list(map(int,input().split())) for i in range(q)]

from random import randint








A = []
for i in range(q):
    if Q[i][0] == 1:
        A.append((Q[i][1], i))
A.sort()
D = {}
for i in range(len(A)):
    D[A[i]] = i+1

B = Bit(len(D) + 2)



asum = 0
bsum = Q[0][2]
m_ind = D[(Q[0][1], 0)]
B.add(D[(Q[0][1], 0)], 1)
ok_a = 1
for i in range(1, q):
    if Q[i][0] == 2:
        
        print(A[m_ind-1][0], asum+bsum)
    else:
        bsum += Q[i][2]
        B.add(D[(Q[i][1], i)], 1)
        
        if ok_a % 2 == 0 and D[(Q[i][1], i)] > m_ind:
            ng = 0
            ok = len(D)+2
            m = (ok+ng) // 2
            while abs(ok-ng) > 1:
                if B.sum(m) >= ok_a//2 + 1:
                    ok = m
                else:
                    ng = m
                m = (ok+ng) // 2
            m_ind = ok
        elif ok_a % 2 == 1 and D[(Q[i][1], i)] < m_ind:
            ng = 0
            
            
            ok = len(D)+2
            m = (ok+ng) // 2
            while abs(ok-ng) > 1:
                if B.sum(m) >= ok_a//2 + 1:
                    ok = m
                else:
                    ng = m
                m = (ok+ng) // 2
            
            asum += abs(A[ok-1][0]-A[m_ind-1][0])
            m_ind = ok
            
        asum += abs(Q[i][1]-A[m_ind-1][0])
        ok_a += 1

Solution (Python):
import sys
import io, os

input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

q = int(input())

import heapq
L = []
R = []
heapq.heapify(L)
heapq.heapify(R)

B = 0

for i in range(q):
    query = list(map(int, input().split()))
    if query[0] == 1:
        a, b = query[1], query[2]
        B += b
        heapq.heappush(L, -a)
        heapq.heappush(R, a)
        if -L[0] > R[0]:
            l = -heapq.heappop(L)
            r = heapq.heappop(R)
            B += l-r
            heapq.heappush(L, -r)
            heapq.heappush(R, l)
    else:
        print(-L[0], B)

Solution (Python):
import sys
import io, os

input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

q = int(input())

import heapq
L = []
R = []
heapq.heapify(L)
heapq.heapify(R)

B = 0

for i in range(q):
    query = list(map(int, input().split()))
    if query[0] == 1:
        a, b = query[1], query[2]
        B += b
        heapq.heappush(L, -a)
        heapq.heappush(R, a)
        if -L[0] > R[0]:
            l = -heapq.heappop(L)
            r = heapq.heappop(R)
            B += l-r
            heapq.heappush(L, -r)
            heapq.heappush(R, l)
    else:
        print(-L[0], B)

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]



def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


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


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count




Q = I()
data = ILL(Q)

As = {-10**10,10**10}
for temp in data:
  if len(temp) == 3:
    As.add(temp[1])
    
As = list(As)
As.sort()

dic = DD(int)
for i in range(len(As)):
  dic[As[i]] = i 
  
class BIT:
  def __init__(self, logn):
    self.n = 1<<logn
    self.data = [0]*(self.n+1)
    self.el = [0]*(self.n+1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def get(self, i, j=None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i)
  def bisect(self, x):
    w = i = 0
    k = self.n
    while k:
      if i+k <= self.n and w + self.data[i+k] < x:
        w += self.data[i+k]
        i += k
      k >>= 1
    return i+1

class BIT_RSQ_RAQ:
  def __init__(self, N):
    self.N = N
    self.data0 = [0]*(self.N+1)
    self.data1 = [0]*(self.N+1)
  def _add(self, data, k, x):
    while k <= self.N:
      data[k] += x
      k += k & -k
  def add(self, l, r, x):
    self._add(self.data0, l, -x*(l-1))
    self._add(self.data0, r, x*(r-1))
    self._add(self.data1, l, x)
    self._add(self.data1, r, -x)
  def _get(self, data, k):
    s = 0
    while k:
      s += data[k]
      k -= k & -k
    return s
  def query(self, l, r):
    return self._get(self.data1, r-1) * (r-1) + self._get(self.data0, r-1) - self._get(self.data1, l-1) * (l-1) - self._get(self.data0, l-1)

N = len(As)
B = BIT(int_log(N,2)+1)
ACC1 = BIT_RSQ_RAQ(N)
ACC2 = BIT_RSQ_RAQ(N)

base = 0
count = 0
for temp in data:
  if len(temp) == 3:
    _,a,b = temp
    ACC1.add(1,dic[a]+1,a+10**10)
    ACC2.add(dic[a]+2,N+1,10**10-a)
    base += b
    count += 1
    B.add(dic[a],1)
  else:
    x = As[B.bisect((count+1)//2)]
    
    print(x,ACC1.query(dic[x]+1,dic[x]+2)-(x+10**10)*(count-B.sum(dic[x]))+ACC2.query(dic[x]+1,dic[x]+2)-(10**10-x)*(B.sum(dic[x]-1))+base)

Solution (Python):
q=int(input())
query=[input() for _ in range(q)]
from bisect import bisect_left
ary=[-float('inf')]
for qq in query:
  if qq[0]=='1':
    _,a,_=map(int,qq.split())
    ary.append(a)
ary.sort()
ary.append(float('inf'))

class BIT:
  def __init__(self, n):
    self.n = n
    self.data = [0]*(n+1)
    self.el = [0]*(n+1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def get(self, i, j=None):
    if j is None:
        return self.el[i]
    return self.sum(j) - self.sum(i)

ml,mr=0,len(ary)+1
mv=0
bit=BIT(len(ary)+1)
for qq in query:
  if qq[0]=='2':
    print(ary[ml],mv)
  else:
    _,a,b=map(int,qq.split())
    a=bisect_left(ary,a)
    bit.add(1,-1)
    bit.add(a+1,2)
    if ml<=a<mr:
      mv+=b
      ml,mr=a,a+1
    else:
      l,r=1,len(ary)+2
      
      while r-l>1:
        x=(r+l)//2
        if bit.sum(x)>=0:
          l,r=l,x
        else:
          l,r=x,r
      
      mv+=b
      mv+=min(abs(ary[l]-ary[ml]),abs(ary[l]-ary[mr]))+abs(ary[l]-ary[a])
      ml=l
      l,r=1,len(ary)+2
      while r-l>1:
        x=(r+l)//2
        if bit.sum(x)>0:
          l,r=l,x
        else:
          l,r=x,r
      mr=l

Solution (Python):
q=int(input())
query=[input() for _ in range(q)]
from bisect import bisect_left
ary=[-float('inf')]
for qq in query:
  if qq[0]=='1':
    _,a,_=map(int,qq.split())
    ary.append(a)
ary.sort()
ary.append(float('inf'))

class SegmentTree():
  def __init__(self,size,f=lambda x,y:x+y,default=0):
    self.size=pow(2,(size-1).bit_length())
    self.f=f
    self.default=default
    self.data=[default]*(self.size*2)
  def update(self,i,x):
    i+=self.size
    self.data[i]=x
    while i:
      i>>=1
      self.data[i]=self.f(self.data[i*2],self.data[i*2+1])
  
  def query(self,l,r):
    l,r=l+self.size,r+self.size
    lret,rret=self.default,self.default
    while l<r:
      if l&1:
        lret=self.f(self.data[l],lret)
        l+=1
      if r&1:
        r-=1
        rret=self.f(self.data[r],rret)
      l>>=1
      r>>=1
    return self.f(lret,rret)
  def get(self,i):
    return self.data[self.size+i]
  def add(self,i,x):
    self.update(i,self.get(i)+x)

ml,mr=0,len(ary)+1
mv=0
st=SegmentTree(len(ary))
for qq in query:
  if qq[0]=='2':
    print(ary[ml],mv)
  else:
    _,a,b=map(int,qq.split())
    a=bisect_left(ary,a)
    st.add(0,-1)
    st.add(a,2)
    if ml<=a<mr:
      mv+=b
      ml,mr=a,a+1
    else:
      l,r=0,len(ary)+1
      
      while r-l>1:
        x=(r+l)//2
        if st.query(0,x)>=0:
          l,r=l,x
        else:
          l,r=x,r
      
      mv+=b
      mv+=min(abs(ary[l]-ary[ml]),abs(ary[l]-ary[mr]))+abs(ary[l]-ary[a])
      ml=l
      l,r=0,len(ary)+1
      while r-l>1:
        x=(r+l)//2
        if st.query(0,x)>0:
          l,r=l,x
        else:
          l,r=x,r
      mr=l

Solution (Python):
from bisect import bisect_left
q=int(input())
query=[input() for _ in range(q)]
l,r=-pow(10,9),pow(10,9)
ary=[-float('inf')]
for qq in query:
    if qq[0]=='1':
        _,a,b=map(int,qq.split())
        ary.append(a)
ary.append(float('inf'))
ary.sort()

class SegmentTree():
    def __init__(self,size,segfunc=lambda x,y:x+y,default=0):
        self.segfunc=segfunc
        self.default=default
        self.size=pow(2,(size-1).bit_length())
        self.data=[default]*(self.size*2)
    def update(self,i,v):
        i+=self.size
        self.data[i]=v
        while i:
            i>>=1
            self.data[i]=self.segfunc(self.data[2*i],self.data[2*i+1])
    
    def query(self,l,r):
        l+=self.size
        r+=self.size
        lres,rres=self.default,self.default
        while l<r:
            if l&1:
                lres=self.segfunc(lres, self.data[l])
                l += 1
            if r&1:
                r-=1
                rres=self.segfunc(self.data[r],rres)
            l>>=1
            r>>=1
        res=self.segfunc(lres,rres)
        return res
    def get(self,i):
        return self.data[self.size+i]
    def add(self,i,v):
        self.update(i,self.get(i)+v)
    

ml,mr=0,len(ary)+1
mv=0
st=SegmentTree(len(ary))
for qq in query:
    if qq[0]=='2':
        print(ary[ml],mv)
    else:
        _,a,b=map(int,qq.split())
        a=bisect_left(ary,a)
        st.add(0,-1)
        st.add(a,2)
        if ml<=a<mr:
            mv+=b
            ml,mr=a,a+1
        else:
            l,r=0,len(ary)+1
            mv+=b
            while r-l>1:
                x=(l+r)//2
                chk=st.query(0,x)
                if chk>=0:
                    l,r=l,x
                else:
                    l,r=x,r
            l0,r0=l,r
            l,r=ml,len(ary)+1
            while r-l>1:
                x=(l+r)//2
                chk=st.query(0,x)
                if chk>0:
                    l,r=l,x
                else:
                    l,r=x,r
            mv+=min(abs(ary[ml]-ary[l0]),abs(ary[mr]-ary[l0]))+abs(ary[a]-ary[l0])
            mr=l if st.query(0,l+1)>0 else l+1
            ml=l0 if st.query(0,l0+1)>=0 else l0+1

Solution (Python):
from bisect import bisect

Q = int(input())
xs = [-10 ** 10, 10 ** 10]
min_index = 0
minimum = 0
for _ in range(Q):
    s = input()
    if s[0] == '1':
        a, b = map(int, s[2:].split())
        index = bisect(xs, a)
        xs.insert(index, a)
        
        if min_index >= index:
            min_index += 1 
        minimum += abs(xs[min_index] - a) + b
        
        if min_index < (len(xs) - 1) // 2:
            minimum += ((len(xs) % 2) - 2) * (xs[min_index + 1] - xs[min_index])
            min_index += 1
        elif min_index > (len(xs) - 1) // 2:
            minimum += (len(xs) % 2) * (xs[min_index - 1] - xs[min_index])
            min_index -= 1
    else:
        print(xs[min_index], minimum)

Solution (Python):
from heapq import heappop, heappush
class MedianContainer:
    def __init__(self):
        self._left_q = []
        self._right_q = []
        self._left_sum = 0
        self._right_sum = 0
        self._med1, self._med2 = None, None
        self._med = None

    def insert(self, x):
        if not any([self._med, self._med1, self._med2]): 
            self._med = x
        elif self._med is None and self._med1 is not None and self._med2 is not None:
            if x <= self._med1:
                heappush(self._left_q, x*(-1))
                heappush(self._right_q, self._med2)
                self._left_sum += x
                self._right_sum += self._med2
                self._med = self._med1
            elif x >= self._med2:
                heappush(self._left_q, self._med1*(-1))
                heappush(self._right_q, x)
                self._left_sum += self._med1
                self._right_sum += x
                self._med = self._med2
            else:
                heappush(self._left_q, self._med1*(-1))
                heappush(self._right_q, self._med2)
                self._left_sum += self._med1
                self._right_sum += self._med2
                self._med = x
            self._med1, self._med2 = None, None
        else:
            if x <= self._med:
                heappush(self._left_q, x*(-1))
                self._med1 = heappop(self._left_q)*(-1)
                self._left_sum += x
                self._left_sum -= self._med1
                self._med2 = self._med
            else:
                heappush(self._right_q, x)
                self._right_sum += x
                self._med1 = self._med
                self._med2 = heappop(self._right_q)
                self._right_sum -= self._med2
            self._med = None

        
    def get_med(self):
        if self._med is not None:
            return [self._med]
        else:
            return [self._med1, self._med2]


    def get_left_sum(self):
        return self._left_sum


    def get_right_sum(self):
        return self._right_sum


    def get_half_len(self):
        return len(self._left_q)

q = int(input())
const_b = 0
ansl = []

mc = MedianContainer()
for _ in range(q):
    row = list(input().split())
    if row[0] == '2':
        half_len = mc.get_half_len()
        meds = mc.get_med()
        if len(meds) == 1:
            left_sum = meds[0]*half_len - mc.get_left_sum()
            right_sum = mc.get_right_sum() - meds[0]*half_len
            ans = left_sum + right_sum + const_b
            ansl.append((meds[0],ans))
        else:
            left_sum = meds[0]*half_len - mc.get_left_sum()
            right_sum = mc.get_right_sum() - meds[0]*half_len
            ans = left_sum + right_sum + (meds[1]-meds[0]) + const_b
            ansl.append((meds[0],ans))
    
    else:
        a,b = int(row[1]), int(row[2])
        const_b += b
        mc.insert(a)


for ax,av in ansl:
    print(ax,av)