;; -*- 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
(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)

(defconstant +updater-identity+ 0)

(declaim (inline updater-op))
(defun updater-op (a b)
  "Is the operator to compute and update LAZY value."
  (+ a b))

(declaim (inline modifier-op))
(defun modifier-op (a b size)
  "Is the operator to update ACCUMULATOR based on LAZY value."
  (declare (ignore size))
  (+ a b))

(defstruct (inode (:constructor %make-inode (value priority &key left right (count 1) (accumulator +op-identity+) (lazy +updater-identity+) reversed))
                  (:copier nil)
                  (:conc-name %inode-))
  (value +op-identity+ :type fixnum)
  (accumulator +op-identity+ :type fixnum) ; e.g. MIN, MAX, SUM, ...
  (lazy +updater-identity+ :type fixnum)
  (reversed nil :type boolean)
  (priority 0 :type (integer 0 #.most-positive-fixnum))
  (count 1 :type (integer 0 #.most-positive-fixnum))
  (left nil :type (or null inode))
  (right nil :type (or null inode)))

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

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

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

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

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

(declaim (inline force-down))
(defun force-down (inode)
  (declare (inode inode))
  (when (%inode-reversed inode)
    (setf (%inode-reversed inode) nil)
    (rotatef (%inode-left inode) (%inode-right inode))
    (let ((left (%inode-left inode)))
      (when left
        (setf (%inode-reversed left) (not (%inode-reversed left)))))
    (let ((right (%inode-right inode)))
      (when right
        (setf (%inode-reversed right) (not (%inode-reversed right))))))
  (unless (eql +updater-identity+ (%inode-lazy inode))
    (when (%inode-left inode)
      (setf (%inode-lazy (%inode-left inode))
            (updater-op (%inode-lazy (%inode-left inode))
                        (%inode-lazy inode)))
      (setf (%inode-accumulator (%inode-left inode))
            (modifier-op (%inode-accumulator (%inode-left inode))
                         (%inode-lazy inode)
                         (%inode-count (%inode-left inode)))))
    (when (%inode-right inode)
      (setf (%inode-lazy (%inode-right inode))
            (updater-op (%inode-lazy (%inode-right inode))
                        (%inode-lazy inode)))
      (setf (%inode-accumulator (%inode-right inode))
            (modifier-op (%inode-accumulator (%inode-right inode))
                         (%inode-lazy inode)
                         (%inode-count (%inode-right inode)))))
    (setf (%inode-value inode)
          (modifier-op (%inode-value inode)
                       (%inode-lazy inode)
                       1))
    (setf (%inode-lazy inode) +updater-identity+)))

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

(defun inode-merge (left right)
  "Destructively merges two INODEs."
  (declare ((or null inode) left right))
  (cond ((null left) (when right (force-down right) (force-self right)) right)
        ((null right) (when left (force-down left) (force-self left)) left)
        (t (force-down left)
           (force-down right)
           (if (> (%inode-priority left) (%inode-priority right))
               (progn
                 (setf (%inode-right left)
                       (inode-merge (%inode-right left) right))
                 (force-self left)
                 left)
               (progn
                 (setf (%inode-left right)
                       (inode-merge left (%inode-left right)))
                 (force-self right)
                 right)))))

;; (define-condition invalid-itreap-index-error (type-error)
;;   ((itreap :initarg :itreap :reader invalid-itreap-index-error-itreap)
;;    (index :initarg :index :reader invalid-itreap-index-error-index))
;;   (:report
;;    (lambda (condition stream)
;;      (format stream "Invalid index ~W for itreap ~S."
;;              (invalid-itreap-index-error-index condition)
;;              (invalid-itreap-index-error-itreap condition)))))

(declaim (inline inode-insert))
(defun inode-insert (inode index obj)
  "Destructively inserts OBJ into INODE at INDEX."
  (declare ((or null inode) inode)
           ((integer 0 #.most-positive-fixnum) index))
  (assert (<= index (inode-count inode)))
  (let ((obj-inode (%make-inode obj (random most-positive-fixnum))))
    (multiple-value-bind (left right)
        (inode-split inode index)
      (inode-merge (inode-merge left obj-inode) right))))

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

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

(defmacro do-inode ((var inode &optional result) &body body)
  "Successively binds INODE[0], ..., INODE[SIZE-1] to VAR and executes BODY."
  `(block nil
     (inode-map (lambda (,var) ,@body) ,inode)
     ,result))

(defun inode (&rest args)
  ;; TODO: Currently takes O(nlog(n)) time though it can be reduced to O(n).
  (labels ((recurse (list position inode)
             (declare ((integer 0 #.most-positive-fixnum) position))
             (if (null list)
                 inode
                 (recurse (cdr list)
                          (1+ position)
                          (inode-insert inode position (car list))))))
    (recurse args 0 nil)))

(declaim (inline make-inode))
(defun make-inode (size)
  "Makes a treap of SIZE in O(SIZE). The values are filled with the identity
element."
  (labels ((heapify (top)
             (when top
               (let ((prioritized-node top))
                 (when (and (%inode-left top)
                            (> (%inode-priority (%inode-left top))
                               (%inode-priority prioritized-node)))
                   (setq prioritized-node (%inode-left top)))
                 (when (and (%inode-right top)
                            (> (%inode-priority (%inode-right top))
                               (%inode-priority prioritized-node)))
                   (setq prioritized-node (%inode-right top)))
                 (unless (eql prioritized-node top)
                   (rotatef (%inode-priority prioritized-node)
                            (%inode-priority top))
                   (heapify prioritized-node)))))
           (build (l r)
             (declare ((integer 0 #.most-positive-fixnum) l r))
             (if (= l r)
                 nil
                 (let* ((mid (ash (+ l r) -1))
                        (node (%make-inode +op-identity+
                                           (random most-positive-fixnum))))
                   (setf (%inode-left node) (build l mid))
                   (setf (%inode-right node) (build (+ mid 1) r))
                   (heapify node)
                   (update-count node)
                   node))))
    (build 0 size)))

(declaim (inline inode-delete))
(defun inode-delete (inode index)
  (declare ((integer 0 #.most-positive-fixnum) index))
  (assert (< index (inode-count inode)))
  (multiple-value-bind (inode1 inode2)
      (inode-split inode (1+ index))
    (multiple-value-bind (inode1 _)
        (inode-split inode1 index)
      (declare (ignore _))
      (inode-merge inode1 inode2))))

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

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

(defun copy-inode (inode)
  "For development. Recursively copies the whole INODEs."
  (if (null inode)
      nil
      (%make-inode (%inode-value inode)
                   (%inode-priority inode)
                   :left (copy-inode (%inode-left inode))
                   :right (copy-inode (%inode-right inode))
                   :count (%inode-count inode)
                   :accumulator (%inode-accumulator inode)
                   :lazy (%inode-lazy inode)
                   :reversed (%inode-reversed inode))))

(defun inode-bisect-left (threshold treap &key (test #'<))
  "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 test))
  (labels ((recur (count treap)
             (declare ((integer 0 #.most-positive-fixnum) count))
             (cond ((null treap) nil)
                   ((funcall test (%inode-value treap) threshold)
                    (recur count (%inode-right treap)))
                   (t (let ((left-count (- count (inode-count (%inode-right treap)) 1)))
                        (let ((idx (recur left-count (%inode-left treap))))
                          (if idx
                              idx
                              left-count)))))))
    (or (recur (inode-count treap) treap)
        (inode-count treap))))

;; FIXME: might be problematic when two priorities collide.
(declaim (inline inode-query))
(defun inode-query (inode l r)
  (declare ((integer 0 #.most-positive-fixnum) l r))
  (unless (< l r)
    (return-from inode-query 0))
  (assert (<= r (inode-count inode)))
  (multiple-value-bind (inode-0-l inode-l-n)
      (inode-split inode l)
    (multiple-value-bind (inode-l-r inode-r-n)
        (inode-split inode-l-n (- r l))
      (prog1 (%inode-accumulator inode-l-r)
        (inode-merge inode-0-l (inode-merge inode-l-r inode-r-n))))))

(declaim (inline inode-reverse))
(defun inode-reverse (inode l r)
  (declare ((integer 0 #.most-positive-fixnum) l r))
  (assert (and (<= l r) (<= r (inode-count inode))))
  (multiple-value-bind (inode-0-l inode-l-n)
      (inode-split inode l)
    (multiple-value-bind (inode-l-r inode-r-n)
        (inode-split inode-l-n (- r l))
      (setf (%inode-reversed inode-l-r) (not (%inode-reversed inode-l-r)))
      (inode-merge inode-0-l (inode-merge inode-l-r inode-r-n)))))

(declaim (inline inode-update))
(defun inode-update (inode x l r)
  "Updates INODE[i] := (OP INODE[i] X) for all i in [l, r)"
  (declare ((integer 0 #.most-positive-fixnum) l r))
  (assert (and (<= l r) (<= r (inode-count inode))))
  (multiple-value-bind (inode-0-l inode-l-n)
      (inode-split inode l)
    (multiple-value-bind (inode-l-r inode-r-n)
        (inode-split inode-l-n (- r l))
      (when inode-l-r
        (setf (%inode-lazy inode-l-r)
              (updater-op (%inode-lazy inode-l-r) x)))
      (inode-merge inode-0-l (inode-merge inode-l-r inode-r-n)))))

(declaim (ftype (function * (values fixnum &optional)) read-fixnum))
(defun read-fixnum (&optional (in *standard-input*))
  (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 ()
  (let* ((q (read))
         (const 0)
         inode)
    (declare (uint32 q))
    (dotimes (i q)
      (let ((id (read-fixnum)))
        (if (= id 1)
            (let ((a (read-fixnum))
                  (b (read-fixnum)))
              (setf inode (inode-insert inode (inode-bisect-left a inode) a))
              (incf const b))
            (let ((count (inode-count inode)))
              (if (oddp count)
                  (let* ((mid (floor count 2))
                         (at (inode-ref inode mid)))
                    (format t
                            "~D ~D~%"
                            at
                            (+ const
                               (inode-query inode (+ mid 1) (inode-count inode))
                               (- (inode-query inode 0 mid)))))
                  (let* ((mid (floor count 2))
                         (at (inode-ref inode (- mid 1))))
                    (format t
                            "~D ~D~%"
                            at
                            (+ const
                               (inode-query inode mid (inode-count inode))
                               (- (inode-query inode 0 mid))))))))))))

#-swank(main)


Measured memory_bytes: 76264