F. Построй XOR на отрезке
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив из $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$, где все числа от $$$1$$$ до $$$2^{12} - 1$$$.

Нужно обработать $$$q$$$ запросов к этому массиву. Каждый запрос задается тремя целыми числами $$$l_i, r_i, x_i$$$: необходимо найти минимальное по размеру множество $$$S = \{s_1, s_2, \dots, s_k\}$$$, для которого выполняются следующие условия:

  • каждое $$$s_j$$$ равно какому-то элементу подмассива с $$$l_i$$$-й позиции по $$$r_i$$$-ю позицию включительно;
  • $$$s_1 \oplus s_2 \oplus \dots \oplus s_k = x_i$$$, где $$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ.
Входные данные

В первой строке задается одно целое число $$$n$$$ ($$$2 \le n \le 10^4$$$).

Во второй строке заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 2^{12} - 1$$$).

В третьей строке задано одно целое число $$$q$$$ ($$$1 \le q \le 10^6$$$).

Далее следуют $$$q$$$ строк, в $$$i$$$-й из которых заданы три целых числа $$$l_i, r_i, x_i$$$ ($$$1 \le l_i \le r_i \le n$$$; $$$1 \le x_i \le 2^{12} - 1$$$).

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

На каждый запрос выведите одно целое число — минимальный размер искомого множества. Если такого множества не существует, выведите $$$0$$$.

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

Рассмотрим запросы из примера:

  • в первом запросе можно выбрать $$$S = \{5, 4\}$$$;
  • во втором запросе можно выбрать $$$S = \{1\}$$$;
  • в третьем запросе можно выбрать $$$S = \{4, 3, 5\}$$$;
  • в четвертом запросе можно выбрать $$$S = \{1, 3, 7\}$$$.