#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3fll;
int dir[4][2] = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};
long long read() {
  long long x = 0, f = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
  return x * f;
}
void wri(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) wri(x / 10);
  putchar(x % 10 + '0');
}
void write(long long x) {
  wri(x);
  puts("");
}
long long ksc(long long a, long long b, long long mod) {
  return ((a * b -
           (long long)((long long)((long double)a / mod * b + 1e-3) * mod)) %
              mod +
          mod) %
         mod;
}
long long ksm1(long long a, long long n, long long mod) {
  long long t = 1;
  for (; n; n >>= 1, (a *= a) %= mod)
    if (n & 1) (t *= a) %= mod;
  return t;
}
long long ksm2(long long a, long long b, long long mod) {
  long long ints = 1;
  while (b) {
    if (b & 1) ints = ksc(ints, a, mod);
    b >>= 1, a = ksc(a, a, mod);
  }
  return ints % mod;
}
int is2pow(long long x) { return x > 0 ? (x & (x - 1)) == 0 : 0; }
long long lowbit(long long x) { return x & -x; }
long long myrand(long long l, long long r) {
  static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
  return uniform_int_distribution<long long>(l, r)(gen);
}
const int N = 1e6 + 5;
const int M = 8192;
pair<int, int> arr[N];
int num[M];
int brr[N];
int n;
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ;
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> arr[i].first, arr[i].second = i;
  sort(arr + 1, arr + 1 + n);
  memset(num, inf, sizeof(num));
  int pos = 1;
  num[0] = 0;
  while (pos <= n) {
    int tmp = 1;
    int mark = arr[pos].first;
    brr[tmp] = arr[pos].second;
    pos++;
    while (pos <= n && arr[pos].first == mark)
      brr[++tmp] = arr[pos].second, pos++;
    for (int i = 0; i < 8192; i++)
      if (num[i] < brr[tmp])
        num[i ^ mark] =
            min(num[i ^ mark],
                brr[lower_bound(brr + 1, brr + 1 + tmp, num[i]) - brr]);
  }
  int ans = 0;
  for (int i = 0; i < 8192; i++)
    if (num[i] != inf) ans++;
  cout << ans << endl;
  for (int i = 0; i < 8192; i++)
    if (num[i] != inf) cout << i << " ";
  cout << endl;
  return 0;
}

### Prompt

Please formulate a CPP solution to the following problem:

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] 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3fll;
int dir[4][2] = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};
long long read() {
  long long x = 0, f = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
  return x * f;
}
void wri(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) wri(x / 10);
  putchar(x % 10 + '0');
}
void write(long long x) {
  wri(x);
  puts("");
}
long long ksc(long long a, long long b, long long mod) {
  return ((a * b -
           (long long)((long long)((long double)a / mod * b + 1e-3) * mod)) %
              mod +
          mod) %
         mod;
}
long long ksm1(long long a, long long n, long long mod) {
  long long t = 1;
  for (; n; n >>= 1, (a *= a) %= mod)
    if (n & 1) (t *= a) %= mod;
  return t;
}
long long ksm2(long long a, long long b, long long mod) {
  long long ints = 1;
  while (b) {
    if (b & 1) ints = ksc(ints, a, mod);
    b >>= 1, a = ksc(a, a, mod);
  }
  return ints % mod;
}
int is2pow(long long x) { return x > 0 ? (x & (x - 1)) == 0 : 0; }
long long lowbit(long long x) { return x & -x; }
long long myrand(long long l, long long r) {
  static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
  return uniform_int_distribution<long long>(l, r)(gen);
}
const int N = 1e6 + 5;
const int M = 8192;
pair<int, int> arr[N];
int num[M];
int brr[N];
int n;
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ;
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> arr[i].first, arr[i].second = i;
  sort(arr + 1, arr + 1 + n);
  memset(num, inf, sizeof(num));
  int pos = 1;
  num[0] = 0;
  while (pos <= n) {
    int tmp = 1;
    int mark = arr[pos].first;
    brr[tmp] = arr[pos].second;
    pos++;
    while (pos <= n && arr[pos].first == mark)
      brr[++tmp] = arr[pos].second, pos++;
    for (int i = 0; i < 8192; i++)
      if (num[i] < brr[tmp])
        num[i ^ mark] =
            min(num[i ^ mark],
                brr[lower_bound(brr + 1, brr + 1 + tmp, num[i]) - brr]);
  }
  int ans = 0;
  for (int i = 0; i < 8192; i++)
    if (num[i] != inf) ans++;
  cout << ans << endl;
  for (int i = 0; i < 8192; i++)
    if (num[i] != inf) cout << i << " ";
  cout << endl;
  return 0;
}

```