Bạn được cho một đồ thị \(G\) vô hướng gồm \(N\) đỉnh. Các đỉnh được đánh số từ \(0\) đến \(N-1\). Ngoài ra, bạn còn được cho ma trận kề của đồ thị này, trong đó \(G[i][j]='Y'\) nếu hai đỉnh \(i,j\) kề nhau ngược lại \(G[i][j]='N'\) nếu hai đỉnh \(i,j\) không kề nhau.

Một chu trình "đơn lẻ" là một dãy các đỉnh \(V[0],V[1],...,V[l-1]\) thoả mãn:

• \(l\) lớn hơn hoặc bằng \(3\)

• \(l\) lẻ

• Tất cả các \(V[i]\) khác nhau từng đôi một

• Với mỗi \(i(0\le i<l-1),V[i]\) và \(V[i+1]\) kề nhau.

• \(V[l-1],V[0]\) kề nhau.

Yêu cầu: In ra kết quả bài toán dưới dạng như sau: \(C[0]\text{ } -1\text{ } C[1]\text{ } -1\text{ } C[2]\text{ } ...-1\text{ } C[n-1]\). Trong đó: Gọi \(C[i]\) là tập chu trình "đơn lẻ" bất kỳ đi qua đỉnh \(i\) của đồ thị \(G\).

Input

• Dòng thứ nhất chứa số nguyên \(N(1\le N\le 50)\) - Số đỉnh của đồ thị

• Tiếp theo ma trận kề thể hiện đồ thị \(G\)

Output

• In ra đáp án cần tìm.

Example

3
NYY
YNY
YYN

11
0 2 1 -1 0 2 1 -1 0 2 1