Description

有 N 个点，你的任务是给这 N 个点连有向边，现在给出这 N 个点之间的关系，如果(i,j)的关系是'Y'表示在最后的图中从 i 到 j 之间有条有向路径，如果是'N'则表示没有有向路径，让你求出一种可行的连边的方案使得每个点的出度之和最小，保证方案唯一。

Format

Input

第一行一个数 N 表示有 N 个点。

接下去是一个 N*N 的矩阵，共 N 行，每行 N 个字符，第 i 行 j 列的字符如果是'Y',表示最终的图中从 i 到 j 要有一条有向路径。

Output

仅一行输出 N 个数，分别表示每个点的出度。

Samples

4
NYYY
NNYY
NNNY
NNNN

1 1 1 0

Limitation

【数据规模】 100%的数据，N<=50,保证矩阵第 i 行第 i 列的字符为'N',并且保证如果 i 行 j 列为 Y，j 行 k 列为 Y，则 i 行 k 列也必为 Y。