Reconstruct the Dancer Permutation

In a recent performance, 1000 dancers wearing unique numbers from 1 to 1000 arranged themselves in a line. Unfortunately, the exact ordering was forgotten. However, for every contiguous interval of dancers the choreographer remembers whether he liked the segment or not. He liked a segment if and only if the number of inversion pairs in that segment was odd. Here, for an interval [i, j] (1 ≤ i ≤ j ≤ n) with dancer permutation P, the inversion count is defined as (\sum_{i \le k < l \le j} \mathbf{1}_{P[k] > P[l]}) and the segment is liked if this sum is odd.

You are given an integer n and, for every contiguous segment, a binary indicator where 1 means the inversion count is odd and 0 means it is even. Note that for any single dancer (segment of length 1) the inversion count is 0 (even). It is guaranteed that the given data is consistent with at least one permutation of ({1,2,\dots,n}).

Your task is to reconstruct any permutation (P) of ({1,2,\dots,n}) that yields exactly the provided inversion parity for every contiguous segment.

Input Format: The first line contains an integer n. The next n lines describe the inversion parity of all contiguous segments. The i-th line contains (n-i+1) space-separated integers where the j-th number on this line is the parity (0 or 1) for the segment [i, i+j-1].

Output Format: Output a permutation of ({1,2,\dots,n}) (space-separated) that is consistent with the given inversion parities.

Hint: Note that the parity of the inversion count for a segment of two consecutive dancers is 1 if and only if the left dancer’s number is greater than the right dancer’s number. Thus, the values corresponding to segments of length 2 give you the adjacent pair comparisons. A standard method can be used to construct the lexicographically smallest permutation matching these adjacent comparisons. For example, if for 1 ≤ i ≤ n-1 the adjacent indicator (d_i\n= b[i][i+1]) is given, you may construct the permutation by iterating i from 1 to n, pushing i onto a stack, and whenever (d_i = 0) (or i = n) popping the stack to form the next portion of the permutation.

inputFormat

The input begins with a single integer n (1 ≤ n ≤ 1000), which represents the number of dancers. Then follow n lines. The i-th line contains exactly (n-i+1) binary integers (each 0 or 1) separated by spaces. The j-th integer on the i-th line denotes the parity of the inversion count (0 for even, 1 for odd) in the contiguous segment consisting of dancers i through i+j-1.

outputFormat

Output a single line consisting of n space‐separated integers — a permutation of the numbers from 1 to n that matches the provided inversion parity indicators for every contiguous segment.

sample

3
0 0 1
0 1
0

1 3 2