D. Матрица перестановок и XOR
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны два целых числа $$$n$$$ и $$$x$$$ ($$$0 \le x \le n-1$$$).

Постройте матрицу $$$A$$$ размера $$$n\times n$$$, удовлетворяющую всем следующим условиям:

  • Для любых $$$1 \le i, j \le n$$$ выполнено $$$0 \le A_{i,j}\le n-1$$$;
  • Каждая строка матрицы $$$A$$$ является перестановкой чисел $$$0, 1, \ldots, n-1$$$;
  • Каждый столбец матрицы $$$A$$$ является перестановкой чисел $$$0, 1, \ldots, n-1$$$;
  • Для любых $$$1 \le i, j\le n-1$$$, $$$$$$ A_{i,j} \oplus A_{i+1,j} \oplus A_{i,j+1} \oplus A_{i+1,j+1} = x. $$$$$$

    Здесь $$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ.

Или определите, что такой матрицы не существует.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 180$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Единственная строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$x$$$ ($$$2\le n\le 2500$$$, $$$0\le x \lt n$$$).

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2500$$$.

Выходные данные

Для каждого набора входных данных выведите $$$-1$$$, если такой матрицы не существует. Иначе выведите $$$n$$$ строк любой подходящей матрицы.

Если существует несколько подходящих матриц, вы можете вывести любую из них.

Пример
Входные данные
5
2 0
2 1
3 0
4 1
4 0
Выходные данные
0 1
1 0
-1
-1
0 2 1 3
2 1 3 0
1 3 0 2
3 0 2 1
0 1 2 3
1 0 3 2
2 3 0 1
3 2 1 0
Примечание

В первом наборе входных данных показанная матрица имеет и строки, и столбцы, являющиеся перестановками $$$0,1$$$, а её единственная соседняя подматрица $$$2\times2$$$ имеет XOR, равный $$$0$$$.

Второй и третий наборы входных данных невозможны. В последних двух наборах входных данных XOR каждой соседней подматрицы $$$2\times2$$$ равен соответственно $$$1$$$ и $$$0$$$.