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

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

(setf *print-circle* t)

(defconstant +op-identity+ most-positive-fixnum)

(declaim (inline op))
(defun op (x y)
  (min x y))

(defconstant +updater-identity+ most-positive-fixnum)

(declaim (inline updater-op))
(defun updater-op (a b)
  "Is the operator to compute and update LAZY value."
  (declare (fixnum a b))
  (min 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))
  (declare (fixnum a b))
  (min a b))

(declaim (inline treap-order))
(defun treap-order (x y)
  (declare (fixnum x y))
  (< x y))

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

(declaim (inline treap-count))
(defun treap-count (treap)
  "Returns the size of the (nullable) TREAP."
  (declare ((or null treap) treap))
  (if (null treap)
      0
      (%treap-count treap)))

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

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

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

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

(declaim (inline force-down))
(defun force-down (treap)
  (declare (treap treap))
  (unless (eql +updater-identity+ (%treap-lazy treap))
    (when (%treap-left treap)
      (setf (%treap-lazy (%treap-left treap))
            (updater-op (%treap-lazy (%treap-left treap))
                        (%treap-lazy treap)))
      (setf (%treap-accumulator (%treap-left treap))
            (modifier-op (%treap-accumulator (%treap-left treap))
                         (%treap-lazy treap)
                         (%treap-count (%treap-left treap)))))
    (when (%treap-right treap)
      (setf (%treap-lazy (%treap-right treap))
            (updater-op (%treap-lazy (%treap-right treap))
                        (%treap-lazy treap)))
      (setf (%treap-accumulator (%treap-right treap))
            (modifier-op (%treap-accumulator (%treap-right treap))
                         (%treap-lazy treap)
                         (%treap-count (%treap-right treap)))))
    (setf (%treap-value treap)
          (modifier-op (%treap-value treap)
                       (%treap-lazy treap)
                       1))
    (setf (%treap-lazy treap) +updater-identity+)))

(defun treap-find (key treap)
  "Finds the key that satisfies (and (not (funcall test key (%treap-key
sub-treap))) (not (funcall test (%treap-key sub-treap) key))) and returns
the corresponding value. Returns NIL if KEY is not contained."
  (declare #.OPT ((or null treap) treap))
  (labels ((recur (treap)
             (unless treap (return-from treap-find nil))
             (force-down treap)
             (prog1
                 (cond ((treap-order key (%treap-key treap))
                        (recur (%treap-left treap)))
                       ((treap-order (%treap-key treap) key)
                        (recur (%treap-right treap)))
                       (t (%treap-value treap)))
               (force-self treap))))
    (recur treap)))

(defun treap-split (key treap)
  "Destructively splits the TREAP with reference to KEY and returns two treaps,
the smaller sub-treap (< KEY) and the larger one (>= KEY)."
  (declare #.OPT ((or null treap) treap))
  (labels ((recur (treap)
             (if (null treap)
                 (values nil nil)
                 (progn
                   (force-down treap)
                   (if (treap-order (%treap-key treap) key)
                       (multiple-value-bind (left right)
                           (recur (%treap-right treap))
                         (setf (%treap-right treap) left)
                         (force-self treap)
                         (values treap right))
                       (multiple-value-bind (left right)
                           (recur (%treap-left treap))
                         (setf (%treap-left treap) right)
                         (force-self treap)
                         (values left treap)))))))
    (recur treap)))

(defun treap-insert (key value treap)
  "Destructively inserts KEY into TREAP and returns the resultant treap. You
cannot rely on the side effect. Use the returned value.

The behavior is undefined when duplicated keys are inserted."
  (declare ((or null treap) treap))
  (labels ((recur (node treap)
             (declare (treap node))
             (unless treap (return-from recur node))
             (force-down treap)
             (if (> (%treap-priority node) (%treap-priority treap))
                 (progn
                   (setf (values (%treap-left node) (%treap-right node))
                         (treap-split (%treap-key node) treap))
                   (force-self node)
                   node)
                 (progn
                   (if (treap-order (%treap-key node) (%treap-key treap))
                       (setf (%treap-left treap)
                             (recur node (%treap-left treap)))
                       (setf (%treap-right treap)
                             (recur node (%treap-right treap))))
                   (force-self treap)
                   treap))))
    (recur (%make-treap key (random most-positive-fixnum) value value) treap)))

(declaim (inline treap-ensure-key))
(defun treap-ensure-key (key value treap &key if-exists)
  "IF-EXISTS := nil | function

Ensures that TREAP contains KEY and assigns VALUE to it if IF-EXISTS is
false. If IF-EXISTS is function and TREAP contains KEY, TREAP-ENSURE-KEY updates
the value by the function instead of overwriting it with VALUE."
  (declare #.OPT
           ((or null function) if-exists)
           ((or null treap) treap))
  (labels ((find-and-update (treap)
             ;; Updates the value slot and returns T if KEY exists
             (unless treap (return-from find-and-update nil))
             (force-down treap)
             (cond ((treap-order key (%treap-key treap))
                    (when (find-and-update (%treap-left treap))
                      (force-self treap)
                      t))
                   ((treap-order (%treap-key treap) key)
                    (when (find-and-update (%treap-right treap))
                      (force-self treap)
                      t))
                   (t (setf (%treap-value treap)
                            (if if-exists
                                (funcall if-exists (%treap-value treap))
                                value))
                      (force-self treap)
                      t))))
    (if (find-and-update treap)
        treap
        (treap-insert key value treap))))

(defun treap-merge (left right)
  "Destructively merges two treaps. Assumes that all keys of LEFT are smaller
 (or larger, depending on the order) than those of RIGHT."
  (declare #.OPT ((or null treap) 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 (> (%treap-priority left) (%treap-priority right))
             (progn
               (setf (%treap-right left)
                     (treap-merge (%treap-right left) right))
               (force-self left)
               left)
             (progn
               (setf (%treap-left right)
                     (treap-merge left (%treap-left right)))
               (force-self right)
               right)))))

(defun treap-map (function treap)
  "Successively applies FUNCTION to TREAP[0], ..., TREAP[SIZE-1]. FUNCTION must
take two arguments: KEY and VALUE."
  (declare (function function))
  (when treap
    (force-down treap)
    (treap-map function (%treap-left treap))
    (funcall function (%treap-key treap) (%treap-value treap))
    (treap-map function (%treap-right treap))
    (force-self treap)))

(defmethod print-object ((object treap) stream)
  (print-unreadable-object (object stream :type t)
    (let ((init t))
      (treap-map (lambda (key value)
                   (if init
                       (setf init nil)
                       (write-char #\  stream))
                   (format stream "<~A . ~A>" key value))
                 object))))


(defun treap-update (treap x left right)
  "Updates TREAP[KEY] := (OP TREAP[KEY] X) for all KEY in [l, r)"
  (declare #.OPT ((or null treap) treap))
  (assert (not (treap-order right left)))
  (multiple-value-bind (treap-0-l treap-l-n)
      (treap-split left treap)
    (multiple-value-bind (treap-l-r treap-r-n)
        (treap-split right treap-l-n)
      (when treap-l-r
        (setf (%treap-lazy treap-l-r)
              (updater-op (%treap-lazy treap-l-r) x)))
      (treap-merge treap-0-l (treap-merge treap-l-r treap-r-n)))))

(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 (inline sort))
  (let* ((n (read))
         (q (read))
         (ds (make-array q :element-type 'uint32))
         (ss (make-array n :element-type 'uint32))
         (ts (make-array n :element-type 'uint32))
         (xs (make-array n :element-type 'uint32))
         treap)
    (declare (uint31 n q))
    (dotimes (i n)
      (let ((s (read-fixnum))
            (end (read-fixnum))
            (x (read-fixnum)))
        (setf (aref ss i) s
              (aref ts i) end
              (aref xs i) x)
        (setf treap (treap-ensure-key (- s x) most-positive-fixnum treap))
        (setf treap (treap-ensure-key (- end x) most-positive-fixnum treap))))
    (dotimes (i q)
      (let ((d (read-fixnum)))
        (setf (aref ds i) d)
        (setf treap (treap-ensure-key d most-positive-fixnum treap))))
    (dotimes (i n)
      (setf  treap
             (treap-update treap
                           (aref xs i)
                           (- (aref ss i) (aref xs i))
                           (- (aref ts i) (aref xs i)))))
    (with-output-buffer
      (dotimes (i q)
        (let ((d (aref ds i)))
          (let ((res (treap-find d treap)))
            (if (< (the fixnum res) most-positive-fixnum)
                (println res)
                (println -1))))))))

#-swank(main)


Measured memory_bytes: 77672