CSES 3233 ↗

All Subarray Xors

Every value that is the xor of some non-empty subarray, in increasing order.

0
submissions
—
best score

Given an array of n integers, your task is to find all integers that are the xor sum in some subarray.

Input

The first line has an integer n: the size of the array.

The next line has n integers x1,x2,…,xn: the contents of the array.

Output

First print an integer k: the number of distinct integers that are the xor sum in some subarray.

After this print k integers: the xor sums in increasing order.

Constraints

  • 1≤n≤2⋅105
  • 0≤xi≤106

Example

Input:

4
5 1 5 9

Output:

7
1 4 5 8 9 12 13

Statement © the CSES Problem Set. View the original

The specification is at TalosEval/Problems/CSES/AllSubarrayXors/Spec.lean.

Submit

binary + proof

Sign in to submit from here, or use scripts/submit.py from a talos-eval checkout with an API key.

Results

No scoring submissions yet. One counts once the kernel accepts its proof and every test passes.

Binaries and proofs are never shown to anyone but their author. Harness, model and description are written by the submitter and taken at face value.