Korney Korneevich and XOR (hard version)
Contest: Codeforces Round 750 (Div. 2)
Difficulty rating: 2400
Tags: binary search, brute force, dp, greedy, two pointers

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 < s_2 < \ldots < s_m$$$.

Input format:
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$$$.

Output format:
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 < \ldots < x_k$$$) — found $$$x$$$ values.

Constraints:
Time limit: 1.5 s
Memory limit: 512.0 MB

Note:
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]$$$

Example input:
4
4 2 2 4

Example output:
4
0 2 4 6

Example input:
8
1 0 1 7 12 5 3 2

Example output:
12
0 1 2 3 4 5 6 7 10 11 12 13

Editorial:
Let's iterate over all numbers of the array and for each number $$$t$$$ maintain a list $$$g_t$$$ of all numbers $$$y$$$, such that it's possible to choose an increasing subsequence on the current prefix, in which $$$xor$$$ of numbers is equal to $$$y$$$, and the last number of that increasing subsequence is less than $$$t$$$.
Let us currently consider the element $$$a_i$$$. Then let's consider elements of $$$g_{a_i}$$$ — there will be all values of $$$xor$$$-s of the subsequences to which we can append the element $$$a_i$$$. If $$$g_{a_i}$$$ contains a value $$$f$$$, then it's possible to get a value $$$f \oplus a_i$$$, then let's add the value $$$f \oplus a_i$$$ to all lists $$$g$$$ from $$$a_i + 1$$$ to the maximal value of $$$a$$$ (if the value that is being added is already in some $$$g$$$-s, it's unnecessary to add it there again).
Let's perform some optimizations for this solution.
1. Let's stop considering the values $$$g_t$$$ that have already been considered. That is, if we have already considered $$$g_t$$$ at some iteration, then let's erase it, but remember that we never need to add the values of $$$xor$$$, that are being erased. That optimization is sufficient to get the asymptotic behaviour $$$O((max\_a)^3)$$$, where $$$max\_a$$$ is the greatest one among all numbers of the array $$$a$$$ (for every number $$$t$$$ and its possible value of $$$xor$$$ $$$f$$$ we will pass over the value $$$t \oplus f$$$ to all states $$$t + 1, \ldots, max\_a$$$; the amount of different $$$t$$$ is $$$O(max\_a)$$$, the amount of $$$f$$$ is $$$O(max\_a)$$$ as well, and the passing of the value each time is performed in $$$O(max\_a)$$$).
2. Let's notice that when we pass some value of $$$xor$$$ equal to $$$f$$$ to elements $$$t + 1, \ldots, max\_a$$$, and find the element $$$r$$$, in which that value of $$$xor$$$ has already been, then the value $$$f$$$ is already in all elements greater than $$$r$$$, and that's why we don't have to add the value $$$f$$$ any further. Using this optimization we can finally get a solution in $$$O(max\_a^2)$$$, since for every value of $$$xor$$$ (the amount of them is $$$O(max\_a)$$$), we perform $$$O(max\_a)$$$ operations.
In total (considering all optimizations), the asymptotic behaviour of the solution is $$$O(n + (max\_a)^2)$$$.