Korney Korneevich and XOR (hard version)
题意翻译
### 题目描述
给一个长度为 $n$ 的序列 $a_1,a_2,\dots,a_n$ ,寻找在 $a$ 的所有递增子序列(可以为空)的异或和中出现的数。
### 输入格式
第一行一个正整数 $n$ 表示序列长度。
第二行 $n$ 个整数表示序列 $a$ 。
### 输出格式
从小到大输出在 $a$ 的所有子序列(可以为空)的异或和中出现的数。
### 数据范围
$1\le n\le10^6,0\le a_i\le5000$ 。
### 样例解释
对于第一个样例:
- 子序列 $\{\}$ 的异或和为 $0$ 。
- 子序列 $\{2\}$ 的异或和为 $2$ 。
- 子序列 $\{4\}$ 的异或和为 $4$ 。
- 子序列 $\{2,4\}$ 的异或和为 $6$ 。
其他子序列的异或和与上述其中一个子序列的异或和相等。
题目描述
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.
输入输出样例
输入样例 #1
4
4 2 2 4
输出样例 #1
4
0 2 4 6
输入样例 #2
8
1 0 1 7 12 5 3 2
输出样例 #2
12
0 1 2 3 4 5 6 7 10 11 12 13
说明
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] $