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 ≥ 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, … , s_m is called increasing if s_1 < s_2 < … < s_m.

Input

The first line contains a single integer n (1 ≤ n ≤ 10^6).

The second line contains n integers a_1, a_2, …, a_n (0 ≤ a_i ≤ 5000) — the elements of the array a.

Output

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, … x_k (0 ≤ x_1 < … < x_k) — found x values.

Examples

Input


4
4 2 2 4


Output


4
0 2 4 6 


Input


8
1 0 1 7 12 5 3 2


Output


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

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]

Source: codeforces | Difficulty: VERY_HARD
Tags: Sorting

Amortized analysis

Greedy algorithms

Complete search

Dynamic programming


Solutions:
import sys
input = sys.stdin.readline
mx = 1 << 13
n = int(input())
a = list(map(int, input().split()))
g = [list() for _ in range(5001)]
r = [5001] * mx
r[0] = 0
ans = [False] * mx
ans[0] = True
for x in range(1, 5001):
	g[x].append(0)
for i in range(n):
	for y in g[a[i]]:
		x = a[i] ^ y
		ans[x] = True
		if r[x] > a[i]:
			for val in range(a[i] + 1, r[x]):
				g[val].append(x)
			r[x] = min(r[x], a[i] + 1)
	g[a[i]].clear()
ans = [x for x in range(mx) if ans[x]]
print(len(ans))
print(*ans)


from collections import defaultdict
INF = 1 << 13

def main():
	n = int(input())
	A = list(map(int, input().split()))
	dp = [5001] * INF
	dp[0] = 0
	update = [[0] for i in range(5001)]
	for a in A:
		for x in update[a]:
			y = x ^ a
			cur = dp[y]
			if cur > a:
				dp[y] = a
				for j in range(a + 1, cur):
					update[j].append(y)
		update[a] = []
	ans = []
	for i in range(INF):
		if dp[i] != 5001:
			ans.append(i)
	print(len(ans))
	print(*ans)
main()


MAX = 1 << 13
n = int(input())
d = [MAX] * MAX
d[0] = 0
flag = [0] * (MAX + 1)
for _ in input().split():
	a = int(_)
	if flag[a]:
		continue
	flag[a] = 1
	for i in range(MAX):
		if d[i] < a:
			if d[i ^ a] > a:
				for j in range(a + 1, d[i ^ a] + 1):
					flag[j] = 0
				d[i ^ a] = a
r = [str(i) for i in range(MAX) if d[i] < MAX]
print(len(r))
print(' '.join(r))