Mandy has obtained a tournament graph with $n$ vertices. However, she thinks it is too messy, so she decides to partition all vertices into three non-empty sets: $A, B, C$ (each vertex belongs to exactly one of these sets). There are no restrictions on the edges within each set, but for vertices in different sets, there are the following restrictions:

1. If $x \in A, y \in B$, then the direction of the edge between $x, y$ is $x \to y$.
2. If $x \in B, y \in C$, then the direction of the edge between $x, y$ is $x \to y$.
3. If $x \in C, y \in A$, then the direction of the edge between $x, y$ is $x \to y$.

Mandy does not know how to partition them, so she gives the problem to brz, but brz does not know either, so he has to ask you, the clever one, for help: does a valid partition scheme exist?

Input

The first line contains a single positive integer $n$ ($3 \le n \le 500$), representing that the graph has $n$ vertices.

The next $n-1$ lines, the $i$-th line contains $n-i$ space-separated integers. The $j$-th integer represents $a_{i, i+j}$ ($a_{i, i+j} \in \{0, 1\}$). $a_{x, y} = 1$ indicates the direction of the edge between $x, y$ is $x \to y$, and $a_{x, y} = 0$ indicates the direction of the edge between $x, y$ is $y \to x$.

Output

If no valid scheme exists, output only a single line "0 0 0" (without quotes). Otherwise:

The first line outputs three space-separated positive integers $S_A, S_B, S_C$, representing the number of vertices in sets $A, B, C$ respectively. The second line contains $S_A$ space-separated integers, representing the indices of the vertices in set $A$. The third line contains $S_B$ space-separated integers, representing the indices of the vertices in set $B$. The fourth line contains $S_C$ space-separated integers, representing the indices of the vertices in set $C$.

Examples

Input 1

3
1 0
1

Output 1

1 1 1
1
2
3

Input 2

3
1 1
1

Output 2

0 0 0

Input 3

9
1 0 1 1 1 0 0 0
1 1 1 1 0 0 0
1 1 1 0 0 0
0 1 1 1 1
0 1 1 1
1 1 1
1 0
1

Output 3

3 3 3
1 2 3
6 5 4
7 8 9