#P1582F1. Korney Korneevich and XOR (easy version)
Korney Korneevich and XOR (easy version)
Description
This is an easier version of the problem with smaller constraints.
Korney Korneevich dag up an array $a$ of length $n$. Korney Korneevich has recently read about the operation bitwise 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^5$).
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 500$) — 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.
Input
The first line contains a single integer $n$ ($1 \le n \le 10^5$).
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 500$) — 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, \ldots x_k$ ($0 \le x_1 < \ldots < x_k$) — found $x$ values.
Samples
4
4 2 2 4
4
0 2 4 6
8
1 0 1 7 12 5 3 2
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]$