Given an array \(A\) of length \(N\). For every index \(i\), find the number of distinct non-empty XOR subsequences in the subarray \(A[1,2,....,i]\).

Note:

• \(1\) based indexing is used.
• Two subsequences are said to be distinct if the XOR of the elements present in the subsequences is different.
• A subsequence of a given sequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the order of the remaining elements.

Input format

• First line contains an integer \(N\)
• Next line contains \(N \) space-separated integers denoting the array \(A\)

Output format

Print \(N\) space-separated integers where \(i\)'th integer denoting the number of distinct XOR subsequences of subarray \(A[1,2,....,i]\).

Constraints

\(1 \le N, A[i] < 2^{10}\)