Statement is not available in English language
F. Артем и Массив
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Артема есть массив $$$a$$$ длины $$$n$$$. Ему не нравится, когда в массиве есть различные значения, поэтому он просит вас исправить это.

Вам разрешено выполнять операции, которые преобразуют массив. За одну операцию вы можете выбрать три целых числа $$$l$$$, $$$r$$$, $$$x$$$, если $$$\lceil\frac{n}{2}\rceil \le r - l + 1$$$. Тогда для всех $$$i$$$, что $$$l \le i \le r$$$, применяется изменение $$$a_i = a_i \oplus x$$$, где $$$\oplus$$$ обозначает побитовое «исключающее или».

Скажите, можно ли сделать все элементы массива равными, выполнив не более $$$n - 1$$$ операций.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Затем следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит единственное число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — длина массива.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \lt 2^{30}$$$) — сам массив $$$a$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных в отдельной строке выведите одно целое число — количество операций $$$k$$$ ($$$0 \le k \le n - 1$$$), или $$$- 1$$$, если сделать числа равными невозможно.

В случае, если ответ существует, в следующих $$$k$$$ строках выведите по три целых числа $$$l, r, x$$$ ($$$1 \le l \le r \le n$$$, $$$0 \le x \lt 2^{30}$$$) — описание операций.

Пример
Входные данные
3
4
179 179 179 179
9
4 5 5 7 7 7 6 6 4
7
43 23 483 34 2 48 29
Выходные данные
0
2
2 6 1
4 8 2
6
1 5 50
2 7 60
3 7 500
1 6 45
4 7 449
1 4 32
Примечание

В первом наборе входных данных все числа массива равны, поэтому нам не надо выполнять операции.

Во втором наборе данных достаточно двух операций:

  1. Выполним операцию со значениями $$$l = 2$$$, $$$r = 6$$$, $$$x = 1$$$. После её применения изменятся все элементы со $$$2$$$-го по $$$6$$$-й включительно. Тогда массив будет иметь вид $$$[4, 4, 4, 6, 6, 6, 6, 6, 4]$$$.
  2. Выполним операцию со значениями $$$l = 4$$$, $$$r = 8$$$, $$$x = 2$$$. После её применения изменятся все элементы с $$$4$$$-го по $$$8$$$-й включительно. Тогда массив будет иметь вид $$$[4, 4, 4, 4, 4, 4, 4, 4, 4]$$$.