CF1582F2.Korney Korneevich and XOR (hard version)

This is a harder version of the problem with bigger constraints.

Korney Korneevich dag up an array $a$ of length $n$. Korney Korneevich has recently read about the operation bitwise XOR, so he wished to experiment with it. For this purpose, he decided to find all integers $x \ge 0$ such that there exists an increasing subsequence of the array $a$, in which the bitwise XOR of numbers is equal to $x$.

It didn't take a long time for Korney Korneevich to find all such $x$, and he wants to check his result. That's why he asked you to solve this problem!

A sequence $s$ is a subsequence of a sequence $b$ if $s$ can be obtained from $b$ by deletion of several (possibly, zero or all) elements.

A sequence $s_1, s_2, \ldots , s_m$ is called increasing if $s_1 \lt s_2 \lt \ldots \lt s_m$.

这是约束条件更大的加强版本。

科尔尼·科尔涅耶维奇构造了一个长度为 $n$ 的数组 $a$。科尔尼·科尔涅耶维奇最近学习了按位异或（XOR）运算，因此希望对此进行实验。为此，他决定找出所有满足 $x \ge 0$ 的整数 $x$，使得数组 $a$ 中存在一个严格递增子序列，其所有元素的按位异或结果恰好等于 $x$。

科尔尼·科尔涅耶维奇很快便找出了所有这样的 $x$，现在他想验证自己的结果是否正确。因此，他请你来解决这个问题！

序列 $s$ 是序列 $b$ 的一个子序列，当且仅当 $s$ 可通过从 $b$ 中删除若干（可能为零个或全部）元素而得到。

序列 $s_1, s_2, \ldots , s_m$ 被称为严格递增的，当且仅当 $s_1 \lt s_2 \lt \ldots \lt s_m$。

The first line contains a single integer $n$ ($1 \le n \le 10^6$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 5000$) — the elements of the array $a$.

第一行包含一个整数 $n$（$1 \le n \le 10^6$）。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le 5000$）——数组 $a$ 的元素。

In the first line print a single integer $k$ — the number of found $x$ values.

In the second line print $k$ integers in increasing order $x_1, x_2, \ldots x_k$ ($0 \le x_1 \lt \ldots \lt x_k$) — found $x$ values.

第一行输出一个整数 $k$ —— 找到的 $x$ 值的个数。

第二行按升序输出 $k$ 个整数 $x_1, x_2, \ldots, x_k$（满足 $0 \le x_1 \lt \ldots \lt x_k$）—— 找到的 $x$ 值。

In the first test case:

• To get value $x = 0$ it is possible to choose and empty subsequence
• To get value $x = 2$ it is possible to choose a subsequence $[2]$
• To get value $x = 4$ it is possible to choose a subsequence $[4]$
• To get value $x = 6$ it is possible to choose a subsequence $[2, 4]$

在第一个测试用例中：

• 要得到值 $x = 0$，可以选择一个空子序列；
• 要得到值 $x = 2$，可以选择子序列 $[2]$；
• 要得到值 $x = 4$，可以选择子序列 $[4]$；
• 要得到值 $x = 6$，可以选择子序列 $[2, 4]$。