;; -*- 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
(declaim (inline delete-adjacent-duplicates))
(defun delete-adjacent-duplicates (seq &key (test #'eql))
  "Destructively deletes adjacent duplicates of SEQ: e.g. #(1 1 1 2 2 1 3) ->
#(1 2 1 3)"
  (declare (sequence seq)
           (function test))
  (etypecase seq
    (vector
     (if (zerop (length seq))
         seq
         (let ((prev (aref seq 0))
               (end 1))
           (loop for pos from 1 below (length seq)
                 unless (funcall test prev (aref seq pos))
                 do (setf prev (aref seq pos)
                          (aref seq end) (aref seq pos)
                          end (+ 1 end)))
           (adjust-array seq end))))
    (list
     (loop for rest on seq
           unless (and (cdr rest)
                       (funcall test (first rest) (second rest)))
           collect (car rest)))))

(declaim (inline make-reverse-lookup-table))
(defun make-reverse-lookup-table (vector &key (test #'eql))
  "Assigns each value of the (usually sorted) VECTOR of length n to the integers
0, ..., n-1."
  (let ((table (make-hash-table :test test :size (length vector))))
    (dotimes (i (length vector) table)
      (setf (gethash (aref vector i) table) i))))

(setf *print-circle* t)

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

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

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

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

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

(defstruct (itreap (:constructor %make-itreap (value priority &key left right (count 1) (accumulator +op-identity+) (lazy +updater-identity+)))
                  (:copier nil)
                  (:conc-name %itreap-))
  (value +op-identity+ :type fixnum)
  (accumulator +op-identity+ :type fixnum) ; e.g. MIN, MAX, SUM, ...
  (lazy +updater-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))
                  (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))

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

(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 ((integer 0 #.most-positive-fixnum) index))
  (unless itreap
    (return-from itreap-split (values nil nil)))
  (force-down itreap)
  (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 ((or null itreap) 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 (> (%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)))))

(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 ~W."
             (invalid-itreap-index-error-index condition)
             (invalid-itreap-index-error-itreap condition)))))

(declaim (inline itreap-insert))
(defun itreap-insert (itreap index obj)
  "Destructively inserts OBJ into ITREAP at INDEX."
  (declare ((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 ((obj-itreap (%make-itreap obj (random most-positive-fixnum))))
    (multiple-value-bind (left right)
        (itreap-split itreap index)
      (itreap-merge (itreap-merge left obj-itreap) right))))

(defun itreap-map (function itreap)
  "Successively applies FUNCTION to ITREAP[0], ..., ITREAP[SIZE-1]."
  (declare (function function))
  (when itreap
    (force-down 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 make-itreap))
(defun make-itreap (size)
  "Makes a treap of SIZE in O(SIZE) time. The values are filled with the
identity element."
  (labels ((heapify (top)
             (when top
               (let ((prioritized-node top))
                 (when (and (%itreap-left top)
                            (> (%itreap-priority (%itreap-left top))
                               (%itreap-priority prioritized-node)))
                   (setq prioritized-node (%itreap-left top)))
                 (when (and (%itreap-right top)
                            (> (%itreap-priority (%itreap-right top))
                               (%itreap-priority prioritized-node)))
                   (setq prioritized-node (%itreap-right top)))
                 (unless (eql prioritized-node top)
                   (rotatef (%itreap-priority prioritized-node)
                            (%itreap-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-itreap +op-identity+
                                           (random most-positive-fixnum))))
                   (setf (%itreap-left node) (build l mid))
                   (setf (%itreap-right node) (build (+ mid 1) r))
                   (heapify node)
                   (update-count node)
                   node))))
    (build 0 size)))

(declaim (inline itreap-delete))
(defun itreap-delete (itreap index)
  (declare ((integer 0 #.most-positive-fixnum) index))
  (unless (< index (itreap-count itreap))
    (error 'invalid-itreap-index-error :itreap itreap :index index))
  (multiple-value-bind (itreap1 itreap2)
      (itreap-split itreap (1+ index))
    (multiple-value-bind (itreap1 _)
        (itreap-split itreap1 index)
      (declare (ignore _))
      (itreap-merge itreap1 itreap2))))

(declaim (inline itreap-ref))
(defun itreap-ref (itreap index)
  (declare ((integer 0 #.most-positive-fixnum) index))
  (unless (< index (itreap-count itreap))
    (error 'invalid-itreap-index-error :itreap itreap :index index))
  (labels ((%ref (itreap index)
             (declare ((integer 0 #.most-positive-fixnum) index))
             (force-down itreap)
             (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 (setf itreap-ref)))
(defun (setf itreap-ref) (new-value itreap index)
  (declare ((integer 0 #.most-positive-fixnum) index))
  (unless (< index (itreap-count itreap))
    (error 'invalid-itreap-index-error :itreap itreap :index index))
  (labels ((%set (itreap index)
             (declare ((integer 0 #.most-positive-fixnum) index))
             (force-down itreap)
             (prog1
                 (let ((left-count (itreap-count (%itreap-left itreap))))
                   (cond ((< index left-count)
                          (%set (%itreap-left itreap) index))
                         ((> index left-count)
                          (%set (%itreap-right itreap) (- index left-count 1)))
                         (t (setf (%itreap-value itreap) new-value))))
               (force-self itreap))))
    (%set itreap index)
    new-value))

(declaim (inline itreap-update))
(defun itreap-update (itreap x l r)
  "Updates ITREAP[i] := (OP ITREAP[i] X) for all i in [l, r)"
  (declare ((integer 0 #.most-positive-fixnum) l r))
  (unless (<= l r (itreap-count itreap))
    (error 'invalid-itreap-index-error :itreap itreap :index (cons l r)))
  (multiple-value-bind (itreap-0-l itreap-l-n)
      (itreap-split itreap l)
    (multiple-value-bind (itreap-l-r itreap-r-n)
        (itreap-split itreap-l-n (- r l))
      (when itreap-l-r
        (setf (%itreap-lazy itreap-l-r)
              (updater-op (%itreap-lazy itreap-l-r) x)))
      (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 (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))
         (table (make-array 0 :element-type 'int32 :fill-pointer 0)))
    (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)
        (vector-push-extend (- s x) table)
        (vector-push-extend (- end x) table)))
    (dotimes (i q)
      (let ((d (read-fixnum)))
        (setf (aref ds i) d)
        (vector-push-extend d table)))
    (setf table (sort table #'<))
    (let ((revs (make-reverse-lookup-table table))
          (itreap (make-itreap (length table))))
      (dotimes (i n)
        (itreap-update itreap (aref xs i)
                       (gethash (- (aref ss i) (aref xs i)) revs)
                       (gethash (- (aref ts i) (aref xs i)) revs)))
      (dotimes (i q)
        (let ((d (aref ds i)))
          (let ((q (itreap-ref itreap (gethash d revs))))
            (if (< q most-positive-fixnum)
                (println q)
                (println -1))))))))

#-swank(main)


;; For Test
#+swank
(defun io-equal (in-string out-string &optional (func #'main))
  (labels ((ensure-last-lf (s)
             (if (and (> (length s) 0)
                      (eql (char s (- (length s) 1)) #\Linefeed))
                 s
                 (uiop:strcat s uiop:+lf+))))
    (equal (ensure-last-lf out-string)
           (with-output-to-string (out)
             (let ((*standard-output* out))
               (with-input-from-string (*standard-input* (ensure-last-lf in-string))
                 (funcall func)))))))

#+swank
(defun get-clipbrd ()
  (with-output-to-string (out)
    (run-program "C:/msys64/usr/bin/cat.exe" '("/dev/clipboard") :output out)))

#+swank (defparameter *this-pathname* (uiop:current-lisp-file-pathname))
#+swank (defparameter *dat-pathname* (uiop:merge-pathnames* "test.dat" *this-pathname*))

#+swank
(defun run (&optional thing (out *standard-output*))
  (let ((*standard-output* out))
    (etypecase thing
      (null ; Runs #'MAIN with the string on clipboard
       (with-input-from-string (*standard-input* (delete #\Return (get-clipbrd)))
         (main)))
      (string
       (with-input-from-string (*standard-input* (delete #\Return thing))
         (main)))
      (symbol (5am:run! thing))
      (pathname ; Runs #'MAIN with the string in a text file
       (with-open-file (*standard-input* thing)
         (main))))))

#+swank
(defun gen-dat ()
  (uiop:with-output-file (out *dat-pathname* :if-exists :supersede)
    (format out "")))

#+swank
(defun bench (&optional (out (make-broadcast-stream)))
  (time (run *dat-pathname* out)))

;; To run: (5am:run! :sample)
#+swank
(it.bese.fiveam:test :sample
  (it.bese.fiveam:is
   (common-lisp-user::io-equal "4 6
1 3 2
7 13 10
18 20 13
3 4 2
0
1
2
3
5
8
"
    "2
2
10
-1
13
-1
")))


Measured memory_bytes: 96864