;; -*- 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 map-permutations!))
(defun map-permutations! (function vector &optional (start 0) end)
  "Destructively permutes VECTOR[START] ... VECTOR[END-1] and applies FUNCTION
to VECTOR each time."
  (declare (function function)
           (vector vector))
  (labels ((recurse (start end)
             (declare ((mod #.array-total-size-limit) start end))
             (if (> start end)
                 (funcall function vector)
                 (progn
                   (recurse (1+ start) end)
                   (loop for i from (1+ start) below end
                         do (rotatef (aref vector start) (aref vector i))
                            (recurse (1+ start) end)
                            (rotatef (aref vector start) (aref vector i)))))))
    (recurse start (or end (length vector)))))

;; I introduce INIT-VECTOR for better type-propagation on SBCL.
#+sbcl
(eval-when (:compile-toplevel :load-toplevel :execute)
  (sb-c:defknown init-vector (vector (mod #.array-total-size-limit))
      vector (sb-c:flushable)
    :overwrite-fndb-silently t)

  (sb-c:defoptimizer (init-vector sb-c:derive-type) ((template size))
    (let* ((template-type (sb-c::lvar-type template))
           (size-value (multiple-value-bind (constantp value) (sb-c::constant-lvar-p size)
                         (when constantp value)))
           (spec `(,(if (sb-kernel:array-type-complexp template-type) 'array 'simple-array)
                   ,(sb-kernel:type-specifier (sb-kernel:array-type-element-type template-type))
                   (,(or size-value '*)))))
      (sb-c::careful-specifier-type spec))))

(defun init-vector (template size)
  "Returns a newly initialized vector of the same type as TEMPLATE vector with
SIZE."
  (declare (optimize (speed 3) (safety 0)))
  (make-array size :element-type (array-element-type template)))

(declaim (inline map-combinations))
(defun map-combinations (function vector &optional k)
  "Applies FUNCTION to each combination of length K of VECTOR. Note that
the vector passed to FUNCTION will be recycled."
  (declare (function function)
           (vector vector))
  (let* ((n (length vector))
         (k (or k n))
         (result (init-vector vector k)))
    (declare ((mod #.array-total-size-limit) k))
    (labels ((recurse (pos prev)
               (if (= pos k)
                   (funcall function result)
                   (loop for i from (1+ prev) below n
                         do (setf (aref result pos) (aref vector i))
                            (recurse (1+ pos) i)))))
      (recurse 0 -1))))

(declaim (inline map-permutations))
(defun map-permutations (function vector &optional k)
  "Applies FUNCTION to each permutation of length K of VECTOR. Note that the
vector passed to FUNCTION will be recycled."
  (declare (function function)
           (vector vector))
  (map-combinations (lambda (c) (map-permutations! function c)) vector k))

(defmacro do-permutations! ((var vector &optional (start 0) end) &body body)
  `(map-permutations! (lambda (,var) ,@body) ,vector ,start ,end))

(defmacro do-combinations ((var vector &optional k) &body body)
  `(map-combinations (lambda (,var) ,@body) ,vector ,k))

(defmacro do-permutations ((var vector &optional k) &body body)
  `(map-permutations (lambda (,var) ,@body) ,vector ,k))

;; (defun test (size)
;;   (let ((vector (make-array size :element-type '(unsigned-byte 32))))
;;     (declare ((simple-array (unsigned-byte 32) (*)) vector))
;;     (dotimes (i size) (setf (aref vector i) i))
;;     (map-permutations #'print vector (ash size -1))))

(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 %test (m)
  (let* ((len (expt 2 (+ m 1)))
         (seq (make-array len :element-type 'uint32)))
    (dotimes (i len)
      (setf (aref seq i) (floor i 2)))
    (do-permutations (perm seq)
      (let ((mem (make-array (expt 2 m) :initial-element -1 :element-type 'int32))
            (k -1))
        (dotimes (pos len (format t "~A: ~A~%" perm k))
          (let ((num (aref perm pos)))
            (if (= (aref mem num) -1)
                (setf (aref mem num) pos)
                (progn (let ((xor (loop with xor = 0
                                        for i from (aref mem num) to pos
                                        do (setf xor (logxor xor (aref perm i)))
                                        finally (return xor))))
                         (if (= k -1)
                             (setf k xor)
                             (unless (= k xor)
                               (return "NA"))))))))))))

(defun %test2 (m k)
  (let* ((len (expt 2 (+ m 1)))
         (seq (make-array len :element-type 'uint32)))
    (dotimes (i len)
      (setf (aref seq i) (floor i 2)))
    (do-permutations (perm seq)
      (let ((mem (make-array (expt 2 m) :initial-element -1 :element-type 'int32)))
        (dotimes (pos len (progn (format t "~A: ~A~%" perm k)
                                 (return-from %test2)))
          (let ((num (aref perm pos)))
            (if (= (aref mem num) -1)
                (setf (aref mem num) pos)
                (progn (let ((xor (loop with xor = 0
                                        for i from (aref mem num) to pos
                                        do (setf xor (logxor xor (aref perm i)))
                                        finally (return xor))))
                         (unless (= k xor)
                           (return "NA")))))))))))
(defun main ()
  (let* ((m (read))
         (k (read))
         (len (expt 2 (+ m 1)))
         (res (make-array len :element-type 'uint32)))
    (if (or (= k (loop with res = 0
                       for i from 0 below (expt 2 m)
                       unless (= i k)
                       do (setf res (logxor res i))
                       finally (return res)))
            (zerop k))
        (progn
          (if (zerop k)
              (dotimes (i len)
                (setf (aref res i) (floor i 2)))
              (let ((index 0))
                (dotimes (num (expt 2 m))
                  (if (= num k)
                      (progn (setf (aref res (- (expt 2 m) 1)) num)
                             (setf (aref res (- len 1)) num))
                      (progn
                        (setf (aref res index) num)
                        (setf (aref res (- len 2 index)) num)
                        (incf index))))))
          (loop with space = nil
                for c across res
                do (if space
                       (format t " ~A" c)
                       (progn
                         (setq space t)
                         (format t "~A" c))))
          (terpri))
        (println -1))))

#-swank(main)


Measured memory_bytes: 43748