Gates

Consider a circuit consisting of $n$ gates, numbered from $0$ to $n-1$. Each gate has some number of inputs and exactly one output. Every input and every output is in one of three states: $0$, $1/2$, or $1$.

Each input is connected to exactly one output of some gate, and the input's state equals the state of the output it is connected to. A single output may be connected to any number of inputs.

Gates $0$ and $1$ are special: they have no inputs at all, and their outputs are always fixed — gate $0$ always outputs $0$, and gate $1$ always outputs $1$.

The state of a gate's output (in short, the gate's state) is valid if one of the following holds:

1. it equals $0$ and the gate has more inputs in state $0$ than in state $1$;
2. it equals $1/2$ and the gate has equally many inputs in state $0$ as in state $1$;
3. it equals $1$ and the gate has more inputs in state $1$ than in state $0$;
4. the gate is special (number $0$ or $1$) and its state is $0$ or $1$ respectively.

A circuit's state is valid if every gate's state is valid. A gate's state is fixed if the gate has the same state in every valid state of the circuit.

Write a program that, for each gate, decides whether its state is fixed and, if so, determines it.

The first line contains the number of gates $n$ ($2 \le n \le 10{,}000$).

The next $n-2$ lines describe the gates' connections. Read from top to bottom, they correspond to gates $2, 3, \dots, n-1$ in order, and the line for gate $i$ describes its inputs. Each such line begins with the number of inputs $k_i$ of that gate ($k_i \ge 1$), followed by $k_i$ gate numbers — the gates whose outputs are connected to the successive inputs of gate $i$. Numbers on a line are separated by single spaces.

The total number of inputs over all gates does not exceed $200{,}000$.

Print $n$ lines. Line $i$ corresponds to gate $i-1$ and must contain:

• 0 — if the state is fixed and equals $0$;
• 1/2 — if the state is fixed and equals $1/2$;
• 1 — if the state is fixed and equals $1$;
• ? — if the state is not fixed.