Given a set of positive integers $S$, let $f_n$ be the number of unlabeled rooted binary trees where the sum of the weights of the nodes is $n$, and the weight of each node is in $S$.
Note that if a tree $T$ can be transformed into $T'$ by swapping the left and right subtrees of any nodes, then $T$ and $T'$ are considered the same tree.
We are only interested in the value of $f_n \bmod 2$. You need to output $f_n \bmod 2$ for all $1 \le n \le N$.
The input is a 01 string, the length of which is $n$. The $i$-th character is 1 if and only if $i \in S$.
Output a 01 string of length $n$. The $i$-th character should be $f_i \bmod 2$.
Examples
Input 1
1101010110
Output 1
1000010110
Note
$f_{1,\dots,10} = [1, 2, 4, 10, 24, 63, 166, 455, 1265, 3580]$.
Input 2
See the provided file ex_modtwo2.in/out. This is a test case with $n=10^4$.
Constraints
| Test Case ID | $n \leq $ |
|---|---|
| $1$ | $10$ |
| $2$ | $20$ |
| $3$ | $100$ |
| $4$ | $300$ |
| $5 \sim 6$ | $5\,000$ |
| $7$ | $30\,000$ |
| $8$ | $50\,000$ |
| $9$ | $70\,000$ |
| $10$ | $100\,000$ |
For $100\%$ of the data, it is guaranteed that $1\leq n\leq 10^5$.