Chef has a sequence $A$ of $N$ integers such that $|A_{i}| ≤ 1$.

For each $x$ such that $-N ≤ x ≤ N$, find the number of non-empty subsequences of $A$ whose sum of elements is $x$. Since that answer may be too large, print this modulo $163,577,857$.

------ Input: ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \ldots, A_{N}$.

------ Output: ------
Output $2N+1$ space-separated integers $C_{0}, C_{1} \ldots C_{2*N}$, where $C_{i}$ denotes the number of non-empty subsequences with sum $(i-N)$, modulo $163,577,857$.

------ Constraints: ------
$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$|A_{i}| ≤ 1$ for each valid $i$
It's guaranteed that the total length of the arrays in one test file doesn't exceed $2*10^{6}$

------ Sample Input: ------

2
2
1 0
3
-1 1 -1

------ Sample Output: ------

0 0 1 2 0
0 1 3 2 1 0 0

------ Explanation: ------
In the first test case, the non-empty subsequences with sum $0$ are $\{0\}$ while the subsequences with sum $1$ are $\{1\}$ and $\{1,0\}$.

见题面

见题面