[AdditionalFile5616.zip](file://AdditionalFile5616.zip?type=additional_file)

#5616. 「PA 2016 Final」Turniej

标签: 传统 | 时间限制: 1000 ms | 内存限制: 256 MiB |

题目描述

题目译自 PA 2016 Final Turniej

Bajtocji 正在举行「史诗战士」（Epiccy Wojownicy）电脑游戏的决赛锦标赛。通过远程预选赛选出的 $n$ 名顶尖选手参加了比赛。锦标赛的过程如下：只要赛场上还剩下至少两名选手，就从尚未被淘汰的选手中随机抽取两人进行对决，败者直接淘汰出局。由于在「史诗战士」中不存在平局，因此在经过 $n-1$ 场对决后，将产生唯一的冠军。

对于某些选手对 $(a, b)$ 而言，他们之间直接对决的胜负关系是确定的。那么，哪些选手有机会获得最终的冠军呢？换句话说，对于哪些选手 $x$，存在一种抽签顺序和比赛结果，能够使选手 $x$ 赢得锦标赛？

输入格式

第一行包含一个整数 $n$ $(2 \leq n \leq 500)$，表示锦标赛开始时的选手人数。选手编号为从 $1$ 到 $n$。

接下来的 $n$ 行中，第 $i$ 行包含一个由 $n$ 个字符组成的字符串 $c_{i, 1} c_{i, 2} \cdots c_{i, n}$。

• 对于每个 $i$，都有 $c_{i, i} = \texttt{X}$。
• 对于 $i \neq j$，字符 $c_{i, j} \in \{\texttt{W}, \texttt{P}, \texttt{?}\}$。
• $c_{i, j} = \texttt{W}$ 表示选手 $i$ 在直接对决中必然战胜选手 $j$。
• $c_{i, j} = \texttt{P}$ 表示选手 $i$ 在直接对决中必然输给选手 $j$。
• $c_{i, j} = \texttt{?}$ 表示选手 $i$ 和选手 $j$ 之间的对决既可能以 $i$ 胜利告终，也可能以 $j$ 胜利告终。

已知 $c_{i, j} = \texttt{W}$ 当且仅当 $c_{j, i} = \texttt{P}$，且 $c_{i, j} = \texttt{?}$ 当且仅当 $c_{j, i} = \texttt{?}$。

输出格式

输出所有有机会赢得锦标赛的选手的编号。编号应按升序排列，每个编号各占一行。

样例

输入

4
XPPP
WX?W
W?XW
WPPX

输出

2
3