;; -*- coding: utf-8 -*-
(eval-when (:compile-toplevel :load-toplevel :execute)
  (defparameter OPT
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0)))
  #+swank (progn (ql:quickload '(:cl-debug-print :fiveam))
                 (shadow :run)
                 (use-package :fiveam)))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)

;; BEGIN_INSERTED_CONTENTS
(defmacro with-output-buffer (&body body)
  "Buffers all outputs to *STANDARD-OUTPUT* in BODY and flushes them to
*STANDARD-OUTPUT* after BODY has been done (without error). Note that only
BASE-CHAR is allowed."
  (let ((out (gensym)))
    `(let ((,out (make-string-output-stream :element-type 'base-char)))
       (let ((*standard-output* ,out))
         ,@body)
       (write-string (get-output-stream-string ,out)))))

(setf *print-circle* t)

;; Treap with implicit key for updating and querying interval.

(declaim (inline op))
(defun op (a b)
  (+ a b))

(defconstant +op-identity+ 0)

(defstruct (itreap (:constructor %make-itreap (value priority &key left right (count 1) (accumulator value)))
                  (:copier nil)
                  (:conc-name %itreap-))
  (value +op-identity+ :type fixnum)
  (accumulator +op-identity+ :type fixnum)
  (priority 0 :type (integer 0 #.most-positive-fixnum))
  (count 1 :type (integer 0 #.most-positive-fixnum))
  (left nil :type (or null itreap))
  (right nil :type (or null itreap)))

(declaim (inline itreap-count))
(defun itreap-count (itreap)
  (declare ((or null itreap) itreap))
  (if itreap
      (%itreap-count itreap)
      0))

(declaim (inline itreap-accumulator))
(defun itreap-accumulator (itreap)
  (declare ((or null itreap) itreap))
  (if itreap
      (%itreap-accumulator itreap)
      +op-identity+))

(declaim (inline update-count))
(defun update-count (itreap)
  (declare (itreap itreap))
  (setf (%itreap-count itreap)
        (+ 1
           (itreap-count (%itreap-left itreap))
           (itreap-count (%itreap-right itreap)))))

(declaim (inline update-accumulator))
(defun update-accumulator (itreap)
  (declare (itreap itreap))
  (setf (%itreap-accumulator itreap)
        (if (%itreap-left itreap)
            (if (%itreap-right itreap)
                (let ((mid (op (%itreap-accumulator (%itreap-left itreap))
                               (%itreap-value itreap))))
                  (declare (dynamic-extent mid) (fixnum mid))
                  (op mid (%itreap-accumulator (%itreap-right itreap))))
                (op (%itreap-accumulator (%itreap-left itreap))
                    (%itreap-value itreap)))
            (if (%itreap-right itreap)
                (op (%itreap-value itreap)
                    (%itreap-accumulator (%itreap-right itreap)))
                (%itreap-value itreap)))))

(declaim (inline force-self))
(defun force-self (itreap)
  (declare (itreap itreap))
  (update-count itreap)
  (update-accumulator itreap))


(defun itreap-split (itreap index)
  "Destructively splits the ITREAP into two nodes [0, INDEX) and [INDEX, N), where N
  is the number of elements of the ITREAP."
  (declare #.OPT ((integer 0 #.most-positive-fixnum) index))
  (unless itreap
    (return-from itreap-split (values nil nil)))
  (let ((implicit-key (1+ (itreap-count (%itreap-left itreap)))))
    (if (< index implicit-key)
        (multiple-value-bind (left right)
            (itreap-split (%itreap-left itreap) index)
          (setf (%itreap-left itreap) right)
          (force-self itreap)
          (values left itreap))
        (multiple-value-bind (left right)
            (itreap-split (%itreap-right itreap) (- index implicit-key))
          (setf (%itreap-right itreap) left)
          (force-self itreap)
          (values itreap right)))))

(defun itreap-merge (left right)
  "Destructively merges two ITREAPs."
  (declare #.OPT ((or null itreap) left right))
  (cond ((null left) (when right (force-self right)) right)
        ((null right) (when left (force-self left)) left)
        (t (if (> (%itreap-priority left) (%itreap-priority right))
               (progn
                 (setf (%itreap-right left)
                       (itreap-merge (%itreap-right left) right))
                 (force-self left)
                 left)
               (progn
                 (setf (%itreap-left right)
                       (itreap-merge left (%itreap-left right)))
                 (force-self right)
                 right)))))

(defun itreap-insert (itreap index obj)
  "Destructively inserts OBJ into ITREAP and returns the resultant treap. You
cannot rely on the side effect. Use the returned value."
  (declare #.OPT
           ((or null itreap) itreap)
           ((integer 0 #.most-positive-fixnum) index))
  (unless (<= index (itreap-count itreap))
    (error 'invalid-itreap-index-error :itreap itreap :index index))
  (let ((node (%make-itreap obj (random most-positive-fixnum))))
    (labels ((recur (itreap pos)
               (declare ((integer 0 #.most-positive-fixnum) pos))
               (unless itreap (return-from recur node))
               (if (> (%itreap-priority node) (%itreap-priority itreap))
                   (progn
                     (setf (values (%itreap-left node) (%itreap-right node))
                           (itreap-split itreap pos))
                     (force-self node)
                     node)
                   (let ((implicit-key (+ 1 (itreap-count (%itreap-left itreap)))))
                     (if (< pos implicit-key)
                         (setf (%itreap-left itreap)
                               (recur (%itreap-left itreap) pos))
                         (setf (%itreap-right itreap)
                               (recur (%itreap-right itreap) (- pos implicit-key))))
                     (force-self itreap)
                     itreap))))
      (recur itreap index))))

(defun itreap-map (function itreap)
  "Successively applies FUNCTION to ITREAP[0], ..., ITREAP[SIZE-1]."
  (declare (function function))
  (when itreap
    (itreap-map function (%itreap-left itreap))
    (funcall function (%itreap-value itreap))
    (itreap-map function (%itreap-right itreap))
    (force-self itreap)))

(defmethod print-object ((object itreap) stream)
  (print-unreadable-object (object stream :type t)
    (let ((size (itreap-count object))
          (index 0))
      (declare ((integer 0 #.most-positive-fixnum) index))
      (itreap-map (lambda (x)
                   (princ x stream)
                   (incf index)
                   (when (< index size)
                     (write-char #\  stream)))
                 object))))

(declaim (inline itreap-ref))
(defun itreap-ref (itreap index)
  (declare ((integer 0 #.most-positive-fixnum) index))
  (assert (< index (itreap-count itreap)))
  (labels ((%ref (itreap index)
             (declare ((integer 0 #.most-positive-fixnum) index))
             (prog1
                 (let ((left-count (itreap-count (%itreap-left itreap))))
                   (cond ((< index left-count)
                          (%ref (%itreap-left itreap) index))
                         ((> index left-count)
                          (%ref (%itreap-right itreap) (- index left-count 1)))
                         (t (%itreap-value itreap))))
               (force-self itreap))))
    (%ref itreap index)))

(declaim (inline itreap-bisect-left))
(defun itreap-bisect-left (threshold treap &key (order #'<))
  "Returns the smallest index and the corresponding key that satisfies
KEY[index] >= THRESHOLD. Returns the size of TREAP and THRESHOLD if KEY[size-1]
< THRESHOLD."
  (declare (function order))
  (labels ((recur (count treap)
             (declare ((integer 0 #.most-positive-fixnum) count))
             (cond ((null treap) nil)
                   ((funcall order (%itreap-value treap) threshold)
                    (recur count (%itreap-right treap)))
                   (t (let ((left-count (- count (itreap-count (%itreap-right treap)) 1)))
                        (or (recur left-count (%itreap-left treap))
                            left-count))))))
    (or (recur (itreap-count treap) treap)
        (itreap-count treap))))

(declaim (inline itreap-query))
(defun itreap-query (itreap &key (start 0) end)
  "Queries the sum of the half-open interval specified by the index: [START,
END). If START (END) is not given, it is assumed to be 0 (the size of ITREAP)."
  (declare ((integer 0 #.most-positive-fixnum) start)
           ((or null (integer 0 #.most-positive-fixnum)) end))
  (if (zerop start)
      (if (null end)
          (itreap-accumulator itreap)
          (multiple-value-bind (itreap-0-r itreap-r-n)
              (itreap-split itreap end)
            (prog1 (itreap-accumulator itreap-0-r)
              (itreap-merge itreap-0-r itreap-r-n))))
      (if (null end)
          (multiple-value-bind (itreap-0-l itreap-l-n)
              (itreap-split itreap start)
            (prog1 (itreap-accumulator itreap-l-n)
              (itreap-merge itreap-0-l itreap-l-n)))
          (progn
            (assert (<= start end))
            (multiple-value-bind (itreap-0-l itreap-l-n)
                (itreap-split itreap start)
              (multiple-value-bind (itreap-l-r itreap-r-n)
                  (itreap-split itreap-l-n end)
                (prog1 (itreap-accumulator itreap-l-r)
                  (itreap-merge itreap-0-l (itreap-merge itreap-l-r itreap-r-n)))))))))

(declaim (ftype (function * (values fixnum &optional)) read-fixnum))
(defun read-fixnum (&optional (in *standard-input*))
  (declare #.OPT)
  (macrolet ((%read-byte ()
               `(the (unsigned-byte 8)
                     #+swank (char-code (read-char in nil #\Nul))
                     #-swank (sb-impl::ansi-stream-read-byte in nil #.(char-code #\Nul) nil))))
    (let* ((minus nil)
           (result (loop (let ((byte (%read-byte)))
                           (cond ((<= 48 byte 57)
                                  (return (- byte 48)))
                                 ((zerop byte) ; #\Nul
                                  ;; (return-from read-fixnum 0)
                                  (error "Read EOF or #\Nul."))
                                 ((= byte #.(char-code #\-))
                                  (setf minus t)))))))
      (declare ((integer 0 #.most-positive-fixnum) result))
      (loop
        (let* ((byte (%read-byte)))
          (if (<= 48 byte 57)
              (setq result (+ (- byte 48) (* 10 (the (integer 0 #.(floor most-positive-fixnum 10)) result))))
              (return (if minus (- result) result))))))))

(defmacro dbg (&rest forms)
  #+swank
  (if (= (length forms) 1)
      `(format *error-output* "~A => ~A~%" ',(car forms) ,(car forms))
      `(format *error-output* "~A => ~A~%" ',forms `(,,@forms)))
  #-swank (declare (ignore forms)))

(defmacro define-int-types (&rest bits)
  `(progn
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "UINT~A" b)) () '(unsigned-byte ,b))) bits)
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "INT~A" b)) () '(signed-byte ,b))) bits)))
(define-int-types 2 4 7 8 15 16 31 32 62 63 64)

(declaim (inline println))
(defun println (obj &optional (stream *standard-output*))
  (let ((*read-default-float-format* 'double-float))
    (prog1 (princ obj stream) (terpri stream))))

(defconstant +mod+ 1000000007)

;; Body

(defun main ()
  (declare #.OPT)
  (let* ((q (read))
         (const 0)
         itreap)
    (declare (uint32 q) (fixnum const))
    (with-output-buffer
      (dotimes (i q)
        (let ((id (read-fixnum)))
          (if (= id 1)
              (let ((a (read-fixnum))
                    (b (read-fixnum)))
                (setf itreap (itreap-insert itreap (itreap-bisect-left a itreap) a))
                (incf const b))
              (let ((count (itreap-count itreap)))
                (if (oddp count)
                    (let* ((mid (floor count 2))
                           (at (itreap-ref itreap mid)))
                      (format t
                              "~D ~D~%"
                              at
                              (+ const
                                 (itreap-query itreap :start (+ mid 1))
                                 (- (itreap-query itreap :end mid)))))
                    (let* ((mid (floor count 2))
                           (at (itreap-ref itreap (- mid 1))))
                      (format t
                              "~D ~D~%"
                              at
                              (+ const
                                 (itreap-query itreap :start mid)
                                 (- (itreap-query itreap :end mid)))))))))))))

#-swank(main)


Measured memory_bytes: 79844