Problem E

The Generalissimo

Problem

Bananistan is a country whose leader is Generalissimo Fulgencio Malasuerte who rose to power by using military force. The power structure in that country is very stratified, organized in a strict hierarchy with the Generalissimo at the top. According to the intelligence gathered, orders are given only from one command center to the ones directly below it. Due to the poor condition of the existing communications, orders may only be issued every hour.

The secret services have been unable to decipher the messages and to identify the command centers. Thus, the only information available is the behavior of each command center. It is known that an order takes one hour to be obeyed. It is also known that each company copies what the one directly above it in the hierarchy did on the previous hour. The Generalissimo is the only one who gives the orders according to his enlightened knowledge.

The problem

Nothing is known, a priori, about the hierarchy of command. The goal of your program is to infer the hierarchy from the behavior of the command centers during a certain length of time.

Input

The input is given by a series of lines, where each line has the status of the command centers at the beginning of the hour. Each line has the status of each command center separated by whitespace. The status is simply a string with a maximum of 10 characters.

Output

The output is given by a line. This line shows, for each command center, the index of the one it obeys, or -1 for the Generalissimo. Indexes are separated by spaces.

Sample Input

a d r d a
a a a a a
r a a r a
d a r d r
r r d r d
d d r d r

a d a d r
a d d d a
d a a d d
a a a a a
a d d a a
d r r d d

d d d d d
d d r d d
d d d d d
d d r d d
d d a d d
d d a d d

Sample Output

-1 4 0 -1 0

2 -1 -1 1 2

Not enough information