F2. Корней Корнеевич и XOR (сложная версия)
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это более сложная версия задачи с большими ограничениями.

Корней Корнеевич откопал массив $$$a$$$ длины $$$n$$$. Корней Корнеевич недавно прочитал в книге про операцию побитового исключающего «ИЛИ» (XOR), поэтому он захотел поэкспериментировать с ней. Для этого он решил найти все целые $$$x \ge 0$$$ такие, что существует возрастающая подпоследовательность массива $$$a$$$, в которой побитовое исключающее «ИЛИ» ее чисел равно $$$x$$$.

Корней Корнеевич довольно быстро нашел все такие $$$x$$$, и хочет проверить свой результат. Для этого он попросил вас решить эту задачу!

Последовательность $$$s$$$ является подпоследовательностью $$$b$$$, если $$$s$$$ может быть получена из $$$b$$$ удалением нескольких (возможно, ни одного или всех) элементов.

Последовательность $$$s_1, s_2, \ldots , s_m$$$ называется возрастающей, если выполняется неравенство: $$$s_1 < s_2 < \ldots < s_m$$$.

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

Первая строка содержит единственное целое число $$$n$$$ ($$$1 \le n \le 10^6$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 5000$$$) — элементы массива $$$a$$$.

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

В первой строке выведите единственное число $$$k$$$ — количество найденных вами $$$x$$$.

Во второй строке выходных данных выведите $$$k$$$ целых неотрицательных целых чисел в возрастающем порядке $$$x_1, x_2, \ldots x_k$$$ ($$$0 \le x_1 < \ldots < x_k$$$) — найденные вами $$$x$$$.

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

В первом наборе входных данных:

  • Чтобы получить значение $$$x = 0$$$ можно выбрать пустую подпоследовательность
  • Чтобы получить значение $$$x = 2$$$ можно выбрать подпоследовательность $$$[2]$$$
  • Чтобы получить значение $$$x = 4$$$ можно выбрать подпоследовательность $$$[4]$$$
  • Чтобы получить значение $$$x = 6$$$ можно выбрать подпоследовательность $$$[2, 4]$$$