Reconstructing the Cow Photograph Order

Farmer John intended to line up his N cows (each with a unique ID) in a specific order A[1...N]. However, when he tried to photograph them, some cows mischievously moved from their positions. In each of the 5 photographs, a group of zero or more cows (not necessarily contiguous) steps out of line, and after the remaining cows close the gaps, the moved cows reinsert themselves in different positions. Importantly, each cow moves in at most one photograph.

Your task is to reconstruct the original intended ordering A given the five photograph orderings. Each photograph is a permutation of the cows that differs from A by the movement of a subset of cows. In at least 3 out of the 5 photographs, every cow appears in its true relative order as in A. Use a pairwise voting scheme: for any two cows X and Y, if X appears before Y in at least 3 photographs, then X should appear before Y in A.

Mathematically, if we denote for cows i and j the number of photographs in which cow i appears before cow j by \(votes(i,j)\), then the intended order satisfies:

\[ votes(i,j) \ge 3 \Longrightarrow i \text{ comes before } j \quad \forall \; i, j \]

inputFormat

Input begins with a single integer N (1 \(\le\) N \(\le\) 20,000), representing the number of cows. This is followed by 5 blocks, each containing a permutation of N space-separated cow ID numbers. Each block represents a photograph taken after some cows (possibly none) have moved.

outputFormat

Output the reconstructed ordering A, with one cow ID per line, representing the intended order that Farmer John arranged before any moves.

sample

5
10 20 30 40 50
10 30 40 20 50
40 10 20 30 50
10 20 50 30 40
20 30 40 50 10

10
20
30
40
50