;; -*- 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))))
#+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)
  "Is the operator to update ACCUMULATOR based on LAZY value."
  (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 &key left right lazy))
                  (:copier nil)
                  (:conc-name %treap-))
  (key 0 :type fixnum)
  (value +op-identity+ :type fixnum)
  (lazy +updater-identity+ :type fixnum)
  (priority 0 :type (integer 0 #.most-positive-fixnum))
  (left nil :type (or null treap))
  (right nil :type (or null 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))))
    (when (%treap-right treap)
      (setf (%treap-lazy (%treap-right treap))
            (updater-op (%treap-lazy (%treap-right treap))
                        (%treap-lazy treap))))
    (setf (%treap-value treap)
          (modifier-op (%treap-value treap)
                       (%treap-lazy treap)))
    (setf (%treap-lazy treap) +updater-identity+)))

(defun treap-bisect (key treap)
  (declare #.OPT ((or null treap) treap))
  (labels ((recur (treap)
             (unless treap (return-from recur nil))
             (force-down treap)
             (if (treap-order key (%treap-key treap))
                 (recur (%treap-left treap))
                 (or (recur (%treap-right treap))
                     treap))))
    (let ((result (recur treap)))
      (if result
          (values (%treap-key result) (%treap-value result))
          (values nil nil)))))

(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)
                         (values treap right))
                       (multiple-value-bind (left right)
                           (recur (%treap-left treap))
                         (setf (%treap-left treap) right)
                         (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 #.OPT ((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))
                   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))))
                   treap))))
    (recur (%make-treap key (random most-positive-fixnum) 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 ((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))
                      t))
                   ((treap-order (%treap-key treap) key)
                    (when (find-and-update (%treap-right treap))
                      t))
                   (t (setf (%treap-value treap)
                            (if if-exists
                                (funcall if-exists (%treap-value treap))
                                value))
                      t))))
    (if (find-and-update treap)
        treap
        (treap-insert key value treap))))

(defconstant +neg-inf+ most-negative-fixnum)
(defconstant +pos-inf+ most-positive-fixnum)
(defun treap-update (treap operand l r)
  (declare #.OPT
           (fixnum l r))
  (labels
      ((recur (treap l r)
         (declare (fixnum l r))
         (when treap
           (if (and (= l +neg-inf+) (= r +pos-inf+))
               (progn
                 (setf (%treap-lazy treap)
                       (updater-op (%treap-lazy treap) operand))
                 (force-down treap))
               (let ((key (%treap-key treap)))
                 (force-down treap)
                 (if (<= l key)
                     (if (< key r)
                         ;; KEY is in [L, R)
                         (progn
                           (setf (%treap-value treap)
                                 (modifier-op (%treap-value treap) operand))
                           (recur (%treap-left treap) l +pos-inf+)
                           (recur (%treap-right treap) +neg-inf+ r))
                         ;; KEY is in [R, +inf)
                         (recur (%treap-left treap) l r))
                     ;; KEY is in [0, L)
                     (recur (%treap-right treap) l r)))))))
    (recur treap l r)
    treap))

(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* ((n (read))
         (q (read))
         (ss (make-array n :element-type 'uint31))
         (ts (make-array n :element-type 'uint31))
         (xs (make-array n :element-type 'uint31))
         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))))
    (setf treap (treap-insert most-positive-fixnum most-positive-fixnum treap))
    (setf treap (treap-insert most-negative-fixnum 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 (read-fixnum))
               (res (nth-value 1 (treap-bisect d treap))))
          (println
           (if (< (the fixnum res) most-positive-fixnum)
               res
               -1)))))))

#-swank(main)


Measured memory_bytes: 86372