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