A14652. 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](https://en.wikipedia.org/wiki/Bitwise_operation#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$ .

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$ .

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.

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