Bar Classification

시간 제한1초메모리 제한1024 MB

요약

한 행이나 한 열을 1로 채운 뒤 최대 N개의 칸을 뒤집어 만든 N x N 이진 격자가 주어질 때, 막대가 열이었는지 행이었는지 아니면 둘 다 가능한지 판별한다.

난이도: 보통10점 중 5점
유형: 구현, 완전 탐색, 그리디
정답자: 아직 제출이 없습니다

문제

You are taking a course on machine learning at your university, and as homework you have been tasked with writing a program that can tell vertical bars from horizontal bars in images. To generate some training data, you use the following method. First, take an $N \times N$ grid, and fill it with zeros. Next, take a row or a column, and fill it with ones. Finally, take at most $N$ arbitrary cells, and flip them. Flipping a cell means changing a zero to a one, or changing a one to a zero.

Generating data this way is easy, but how to generate all the answers? It will take hours to go through the training data manually. If only you had a program that finds all the outputs automatically somehow.

You are given an $N \times N$ matrix that has been generated as in the description. Write a program that finds whether it was a column or a row that was filled with ones, or if it is impossible to determine.

입력

The first line of input consists of an integer $N$ ( $2 \leq N \leq 1000$ ), the size of the grid.

The following $N$ lines each contain a string of length $N$ consisting of zeros and ones. These are the rows of the grid.

It is guaranteed that the input was generated by taking a grid of zeros, putting ones on a row or a column, and then flipping at most $N$ cells.

출력

If the bar was vertical (a column), print "|". If it was horizontal (a row), print "-". If it is impossible to determine (because it could be both), print "+".

예제3

예제 1
입력
```
5
01100
01000
01001
00000
01000
```
예상 출력
```
|
```
예제 2
입력
```
3
111
000
111
```
예상 출력
```
-
```
예제 3
입력
```
3
010
101
010
```
예상 출력
```
+
```