#-swank
(unless (member :child-sbcl *features*)
  (quit
   :unix-status
   (process-exit-code
    (run-program *runtime-pathname*
                 `("--control-stack-size" "128MB"
                   "--noinform" "--disable-ldb" "--lose-on-corruption" "--end-runtime-options"
                   "--eval" "(push :child-sbcl *features*)"
                   "--script" ,(namestring *load-pathname*))
                 :output t :error t :input t))))
(eval-when (:compile-toplevel :load-toplevel :execute)
  (sb-int:defconstant-eqx opt
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0))
    #'equal)
  #+swank (ql:quickload '(:cl-debug-print :fiveam) :silent t)
  #-swank (set-dispatch-macro-character
           #\# #\> (lambda (s c p) (declare (ignore c p)) `(values ,(read s nil nil t)))))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)
#-swank (disable-debugger) ; for CS Academy

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

;; BEGIN_INSERTED_CONTENTS
(macrolet ((def (name fname)
             `(define-modify-macro ,name (new-value) ,fname)))
  (def minf min)
  (def maxf max)
  (def mulf *)
  (def divf /)
  (def iorf logior)
  (def xorf logxor)
  (def andf logand))

;;;
;;; Mo's algorithm
;;;

(deftype mo-integer () 'uint31)

(defstruct (mo (:constructor %make-mo
                   (lefts rights order width))
               (:conc-name %mo-)
               (:copier nil)
               (:predicate nil))
  (lefts nil :type (simple-array mo-integer (*)))
  (rights nil :type (simple-array mo-integer (*)))
  (order nil :type (simple-array (integer 0 #.most-positive-fixnum) (*)))
  (width 0 :type (integer 0 #.most-positive-fixnum))
  (index 0 :type (integer 0 #.most-positive-fixnum))
  (posl 0 :type mo-integer)
  (posr 0 :type mo-integer))

(defun make-mo (bucket-width lefts rights)
  "LEFTS := vector of indices of left-end of queries (inclusive)
RIGHTS := vector of indices of right-end of queries (exclusive)

BUCKET-WIDTH would be better set to N/sqrt(Q) where N is the width of the
universe and Q is the number of queries."
  (declare (optimize (speed 3))
           ((simple-array mo-integer (*)) lefts rights)
           ((integer 0 #.most-positive-fixnum) bucket-width)
           (inline sort))
  (let* ((q (length lefts))
         (order (make-array q :element-type '(integer 0 #.most-positive-fixnum))))
    (assert (= q (length rights)))
    (dotimes (i q) (setf (aref order i) i))
    (setf order (sort order
                      (lambda (x y)
                        (if (= (floor (aref lefts x) bucket-width)
                               (floor (aref lefts y) bucket-width))
                            ;; Even-number [Odd-number] block is in ascending
                            ;; [descending] order w.r.t. the right end.
                            (if (evenp (floor (aref lefts x) bucket-width))
                                (< (aref rights x) (aref rights y))
                                (> (aref rights x) (aref rights y)))
                            (< (aref lefts x) (aref lefts y))))))
    (%make-mo lefts rights order bucket-width)))

(declaim (inline mo-get-current))
(defun mo-get-current (mo)
  "Returns the original index of the current (not yet proessed) query."
  (aref (%mo-order mo) (%mo-index mo)))

(declaim (inline mo-get-previous))
(defun mo-get-previous (mo)
  "Returns the original index of the previous (= last processed) query. Returns
the initial index instead when no queries are processed yet."
  (aref (%mo-order mo) (max 0 (- (%mo-index mo) 1))))

(declaim (inline mo-process4))
(defun mo-process4 (mo extend-l extend-r shrink-l shrink-r)
  "Processes the next query."
  (declare (function extend-l extend-r shrink-l shrink-r))
  (let* ((ord (mo-get-current mo))
         (left (aref (%mo-lefts mo) ord))
         (right (aref (%mo-rights mo) ord))
         (posl (%mo-posl mo))
         (posr (%mo-posr mo)))
    (declare ((integer 0 #.most-positive-fixnum) posl posr))
    (loop while (< left posl)
          do (decf posl)
             (funcall extend-l posl))
    (loop while (< posr right)
          do (funcall extend-r posr)
             (incf posr))
    (loop while (< posl left)
          do (funcall shrink-l posl)
             (incf posl))
    (loop while (< right posr)
          do (decf posr)
             (funcall shrink-r posr))
    (setf (%mo-posl mo) posl
          (%mo-posr mo) posr)
    (incf (%mo-index mo))))

;; PAY ATTENTION TO THE STACK SIZE!


(declaim (ftype (function * (values fixnum &optional)) read-fixnum))
(defun read-fixnum (&optional (in *standard-input*))
  "NOTE: cannot read -2^62"
  (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
                                  (error "Read EOF or #\Nul."))
                                 ((= byte #.(char-code #\-))
                                  (setq 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))))))))

(in-package :cl-user)

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

(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 make-euler-tour (tree)
  (declare (vector tree))
  (let* ((n (length tree))
         (tour (make-array (- (* 2 n) 1) :element-type 'int32 :initial-element 0))
         (left-edges (make-array (- (* 2 n) 1) :element-type 'int32 :initial-element -1))
         (right-edges (make-array (- (* 2 n) 1) :element-type 'int32 :initial-element -1))
         ;; pre-order
         (pres (make-array n :element-type 'int32))
         (index 0))
    (declare ((integer 0 #.most-positive-fixnum) index))
    (labels ((dfs (v parent)
               (setf (aref pres v) index)
               (loop for (child . edge-idx) in (aref tree v)
                     unless (= child parent)
                     do (setf (aref right-edges index) edge-idx)
                        (incf index)
                        (setf (aref tour index) child)
                        (setf (aref left-edges index) edge-idx)
                        (dfs child v)
                        (setf (aref right-edges index) edge-idx)
                        (incf index)
                        (setf (aref tour index) v)
                        (setf (aref left-edges index) edge-idx))))
      (unless (zerop n)
        (dfs 0 -1))
      (values tour pres left-edges right-edges))))

(defun main ()
  (declare #.OPT)
  (let* ((n (read))
         (q (read))
         (graph (make-array n :element-type 'list :initial-element nil))
         (cs (make-array n :element-type 'uint31 :initial-element 0))
         (ds (make-array n :element-type 'uint31 :initial-element 0)))
    (dotimes (i (- n 1))
      (let ((a (- (read-fixnum) 1))
            (b (- (read-fixnum) 1))
            (c (- (read-fixnum) 1))
            (d (read-fixnum)))
        (push (cons a i) (aref graph b))
        (push (cons b i) (aref graph a))
        (setf (aref cs i) c
              (aref ds i) d)))
    (multiple-value-bind (tour pres ledges redges) (make-euler-tour graph)
      (declare ((simple-array int32 (*)) tour pres ledges redges))
      (let ((xs (make-array q :element-type 'uint31 :initial-element 0))
            (ys (make-array q :element-type 'uint31 :initial-element 0))
            (us (make-array q :element-type 'uint31 :initial-element 0))
            (vs (make-array q :element-type 'uint31 :initial-element 0)))
        (dotimes (i q)
          (setf (aref xs i) (- (read-fixnum) 1)
                (aref ys i) (read-fixnum)
                (aref us i) (aref pres (- (read-fixnum) 1))
                (aref vs i) (+ 1 (aref pres (- (read-fixnum) 1)))))
        (let ((mo (make-mo 632 us vs))
              (res (make-array q :element-type 'uint31 :initial-element 0))
              (bits (make-array (- n 1) :element-type 'bit :initial-element 0))
              (nums (make-array n :element-type 'uint31 :initial-element 0))
              (dists (make-array n :element-type 'uint31 :initial-element 0))
              (dist 0))
          (declare (uint62 dist))
          (labels ((flip (eidx)
                     (unless (= -1 eidx)
                       (let ((c (aref cs eidx))
                             (d (aref ds eidx)))
                         (if (zerop (aref bits eidx))
                             (progn
                               (incf (aref nums c))
                               (incf (aref dists c) d)
                               (incf dist d))
                             (progn
                               (decf (aref nums c))
                               (decf (aref dists c) d)
                               (decf dist d)))
                         (xorf (aref bits eidx) 1)))))
            (dotimes (_ q)
              (let ((qidx (mo-get-current mo)))
                (mo-process4 mo
                             (lambda (pos) (flip (aref redges pos)))
                             (lambda (pos) (flip (aref ledges pos)))
                             (lambda (pos) (flip (aref redges pos)))
                             (lambda (pos) (flip (aref ledges pos))))
                (let* ((x (aref xs qidx))
                       (y (aref ys qidx))
                       (value (+ (- dist (aref dists x)) (* (aref nums x) y))))
                  (setf (aref res qidx) value)))))
          (write-string
           (with-output-to-string (*standard-output* nil :element-type 'base-char)
             (map () #'println res))))))))

#-swank (main)

;;;
;;; Test and benchmark
;;;

#+swank
(defun io-equal (in-string out-string &key (function #'main) (test #'equal))
  "Passes IN-STRING to *STANDARD-INPUT*, executes FUNCTION, and returns true if
the string output to *STANDARD-OUTPUT* is equal to OUT-STRING."
  (labels ((ensure-last-lf (s)
             (if (eql (uiop:last-char s) #\Linefeed)
                 s
                 (uiop:strcat s uiop:+lf+))))
    (funcall test
             (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 function)))))))

#+swank
(defun get-clipbrd ()
  (with-output-to-string (out)
    (run-program "powershell.exe" '("-Command" "Get-Clipboard") :output out :search t)))

#+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*))
  "THING := null | string | symbol | pathname

null: run #'MAIN using the text on clipboard as input.
string: run #'MAIN using the string as input.
symbol: alias of FIVEAM:RUN!.
pathname: run #'MAIN using the text file as input."
  (let ((*standard-output* out))
    (etypecase thing
      (null
       (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
       (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 "5 3
1 2 1 10
1 3 2 20
2 4 4 30
5 2 1 40
1 100 1 4
1 100 1 5
3 1000 3 4
"
    "130
200
60
")))


Measured memory_bytes: 52316