Ice Cream

A person states preference relations among several ice creams. For any two ice creams A and B, the information says either that A is preferred to B, that the two are liked about equally, or that B is preferred to A.

If preferences were always transitive, all ice creams could be arranged in one line so that every ice cream earlier in the line is preferred to, or liked about equally as, every ice cream later in the line. Real preferences may fail to be transitive, so this problem uses the weaker condition of consistent preference.

For an arrangement I1, I2, ..., In, the arrangement is sorted by consistent preference if, for every i = 1, 2, ..., n - 1, ice cream Ii is preferred to or liked about equally as ice cream Ii+1.

Given n ice creams numbered 1, 2, ..., n and the preference relation between every pair of ice creams, find an arrangement sorted by consistent preference.

The first line contains an integer n (1 <= n <= 1,000).

Each of the next n lines contains n characters. The j-th character of the i-th of these lines, gi,j, describes the relation between ice cream i and ice cream j.

• If gi,j is '+', ice cream i is preferred to ice cream j.
• If gi,j is '-', ice cream j is preferred to ice cream i.
• If gi,j is '0', the two ice creams are liked about equally.

The character gi,i is always 'x'. For i != j, gi,j and gj,i are consistent: if one side is '+', the other side is '-'; if one side is '0', the other side is also '0'.

Print one line containing the ice cream numbers in an arrangement sorted by consistent preference. If there are several possible arrangements, print any one of them.

If no such arrangement exists, print only -1 on the first line.