The final tournament of the computer game Epic Warriors is taking place in Byteotia. It features $n$ top players selected through remote qualifiers. The tournament will proceed as follows: as long as there are at least two players remaining in the tournament, two players will be drawn from those not yet eliminated. They will play a match against each other, and the loser will be eliminated from the tournament. In Epic Warriors, there are no draws, so after $n - 1$ matches, the winner of the tournament will be known.

For some pairs of players $(a, b)$, it is completely clear who will win their direct match. Which players have a chance to win the tournament? In other words, for which players $x$ does there exist a sequence of draws and tournament matches such that $x$ wins the tournament?

Input

The first line of the input contains a single integer $n$ ($2 \le n \le 500$), representing the initial number of players in the tournament. The players are numbered with integers from $1$ to $n$.

Each of the next $n$ lines contains a string of $n$ characters $c_{i,1}c_{i,2} \dots c_{i,n}$. For every $i$, $c_{i,i} = \text{X}$. Furthermore, for $i \neq j$, $c_{i,j} \in \{\text{W}, \text{P}, ?\}$. $c_{i,j} = \text{W}$ means that player $i$ will win a direct match against player $j$; $c_{i,j} = \text{P}$ means that $i$ will lose a match against $j$, and $c_{i,j} = ?$ means that the match between players $i$ and $j$ can end in either a victory for $i$ or a victory for $j$. It is true that $c_{i,j} = \text{W}$ if and only if $c_{j,i} = \text{P}$, and $c_{i,j} = ?$ if and only if $c_{j,i} = ?$.

Output

Output the numbers of the players who have a chance to win the tournament. The numbers should be printed in increasing order, one number per line.

Examples

Input 1

4
XPPP
WX?W
W?XW
WPPX

Output 1

2
3