F. Камни Нима
ограничение по времени на тест
8 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Как вы, возможно, знаете, в игру «Ним» играют двое на нескольких кучах камней, делая ходы по очереди. За один ход игрок выбирает любую непустую кучу и удаляет из неё любое положительное число камней; тот, кто не может сделать ход, проигрывает.

Алиса хочет сыграть в Ним с Безумным Шляпником на $$$n$$$ кучах $$$s_1, s_2, \ldots, s_n$$$ с различными положительными числами камней, но им уже надоело, потому что они играли в эту игру слишком много раз. Вместо этого Алиса предлагает следующий вариант:

  1. Алиса раскрасит каждую из $$$n$$$ куч в один из $$$k$$$ цветов.
  2. Безумный Шляпник оставит несколько куч одного цвета, а остальные кучи выбросит. (Заметьте, что Безумный Шляпник не обязан выбирать все кучи данного цвета.) Безумный Шляпник должен оставить хотя бы одну кучу.
  3. Алиса и Безумный Шляпник сыграют в Ним на оставшихся кучах, причём Алиса ходит первой.
Помогите Алисе найти раскраску куч в минимальное число цветов, при которой она всегда выигрывает финальную игру в Ним, если оба игрока играют оптимально.

Заметьте, что входные данные заданы в закодированном виде; их описание приведено в разделе «Входные данные». Из-за формата кодирования вам нужно будет решить данную задачу для каждого префикса $$$s_1, s_2, \ldots, s_i$$$. Однако вывести саму раскраску нужно только для всего набора куч $$$s_1, s_2, \ldots, s_n$$$.

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 7000$$$).

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0\le a_i\le 10^9$$$).

Значения $$$s_i$$$ закодированы, а именно: пусть $$$k_i$$$ — минимальное число цветов, необходимое для префикса $$$s_1, s_2, \ldots, s_{i-1}$$$, причём $$$k_1 = 0$$$. Тогда $$$s_i := a_i \oplus k_i$$$, где $$$\oplus$$$ обозначает побитовую операцию XOR. Гарантируется, что $$$1\le s_i \le 2n$$$ и что все $$$s_i$$$ различны.

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

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

Для каждого набора входных данных в первой строке выведите $$$k$$$ — минимальное число цветов, необходимое для всего набора куч.

В $$$i$$$-й из следующих $$$k$$$ строк сначала выведите $$$\ell_i$$$ ($$$1 \leq \ell_i \leq n$$$) — количество куч $$$i$$$-го цвета. Затем выведите $$$\ell_i$$$ целых чисел, представляющих размеры куч $$$i$$$-го цвета.

Если существует несколько решений, выведите любое из них. Можно показать, что ответ всегда существует для всех префиксов.

Пример
Входные данные
3
3
1 3 2
6
1 3 2 6 7 10
9
18 12 17 3 6 4 13 11 9
Выходные данные
2
2 1 2
1 3
2
3 1 2 4
3 3 5 8
3
4 16 4 2 9
4 6 15 18 13
1 11
Примечание

В первом примере мы можем восстановить входные данные следующим образом:

  1. Поскольку $$$k_1 = 0$$$, $$$s_1 := 1\oplus 0 = 1$$$.
  2. Минимальное число цветов, необходимое при игре на $$$[1]$$$, равно $$$1$$$, поэтому $$$k_2 = 1$$$ (так как Алиса может немедленно убрать единственный камень и выиграть игру).
  3. Поскольку $$$k_2 = 1$$$, $$$s_2 := 3\oplus 1 = 2$$$.
  4. Минимальное число цветов, необходимое при игре на $$$[1, 2]$$$, равно $$$1$$$, поэтому $$$k_3 = 1$$$.
  5. Поскольку $$$k_3 = 1$$$, $$$s_3 := 2\oplus 1 = 3$$$.

Таким образом, значения куч равны $$$[1, 2, 3]$$$. Можно показать, что минимальное число цветов здесь равно $$$2$$$, и возможная раскраска такова: первая и вторая куча имеют цвет $$$1$$$, а третья куча — цвет $$$2$$$.