Chandelier Coloring

Alice has a huge chandelier at home. Unlike ordinary lamps, this chandelier is composed of many light bulbs. Only one bulb is directly hanging from the ceiling (bulb 1), and every other bulb is hung from some other bulb, with the condition that the parent of any bulb has a smaller index than that bulb. In other words, the chandelier forms a tree with node 1 as the root.

For an upcoming party, Alice wants to re-color the chandelier. She will paint each bulb in one of several colors with the following restrictions:

• All bulbs of the same color must form a connected set in the tree (i.e. the subgraph induced by the bulbs of one particular color is connected).
• Each color must appear on the same number of bulbs.

Thus, if the tree has n bulbs and if Alice uses k colors then (since every color appears equally often) we must have k | n (i.e. k divides n) and each color will appear exactly \(\frac{n}{k}\) times. It turns out that a necessary and sufficient condition for a valid coloring is that for every non‐root node with subtree size \(s\) (the number of nodes in the subtree rooted at that node), it holds that \[ s \equiv 0 \pmod{\frac{n}{k}}, \] where the subtree is defined in the usual way in a rooted tree. (Note that the case \(k=1\) is always valid, and the case \(k=n\) corresponds to each bulb having a unique color.)

However, Alice is a greedy child. If she finds that the number of valid schemes is too few, or too many, she will be unhappy. Therefore, she will try to adjust the chandelier’s structure according to the following rule. For each bulb with index \(x\) (where \(x \neq 1\)), if originally it was hung on bulb \(f_x\) then Alice will re-hang bulb \(x\) on the bulb \[ \Bigl((f_x+19940105)\bmod (x-1)\Bigr)+1. \] She will perform exactly 9 such adjustments. (Since the number nine is considered huge in ancient Chinese texts, Alice decided that 9 adjustments would be enough.)

Your task is to output the valid coloring schemes for the original tree and for each adjusted tree. Specifically, for each state (the original state and after each of the 9 adjustments, a total of 10 states), you should output a binary string of length n (indexed from 1 to n) where the k-th character is '1' if it is possible to partition the tree into k connected components (i.e. color classes) each of size \(\frac{n}{k}\) (which forces \(k\) to be a divisor of \(n\)), and '0' otherwise.

Note: For a fixed valid k, a simple DFS can be used to check that for every non-root node, the size of its subtree is divisible by \(\frac{n}{k}\). The answer for each state is the binary string for \(k=1,2,\dots,n\) in order.

inputFormat

The input contains:

1. A single integer n (the number of bulbs).
2. A line with n-1 integers: f2, f3, …, fn, where for each \(2 \le x \le n\), \(1 \le f_x < x\) indicates that in the initial state bulb \(x\) is hung on bulb \(f_x\).

It is guaranteed that the structure forms a tree with node 1 as the root.

outputFormat

Output 10 lines. Each line is a binary string of length n corresponding to a state of the chandelier. The first line is for the original state, and then each of the following 9 lines is for a successive adjusted state. In each binary string, the k-th character (for \(1 \le k \le n\)) should be '1' if it is possible to partition the tree into k connected groups with each group containing exactly \(\frac{n}{k}\) bulbs (which implies \(k\) divides \(n\)); otherwise, output '0'.

sample

3
1 1

101
101
101
101
101
101
101
101
101
101