34724번 - 종양 찾기

문제

아코는 세계에서 손꼽히는 혈관 박사이다. 아코는 천재적인 감으로 건강한 혈관과 종양이 있는 혈관을 빠르게 구분해 낼 수 있다. 아코는 동국인들의 건강을 위해 X-ray 사진에서 종양을 판별하는 프로그램을 만들고자 한다.

X-ray에서 종양과 혈관은 모두 1ドル$로 보이게 된다. 그 외의 빈 공간은 모두 0ドル$으로 보인다. 천재 동국이는 X-ray를 다음과 같이 분석한다.

• X-ray 상에서 0ドル$을 포함하지 않는 모든 직사각형을 조사한다.
• 직사각형의 모든 변은 X-ray의 행과 열에 평행하다.

분석 결과는 다음 규칙에 따라 판정한다.

1. 직사각형의 짧은 변을 너비라고 한다.
2. 모든 직사각형의 너비가 1ドル$이면 정상적인 혈관이다.
3. 너비가 1ドル$보다 큰 직사각형이 하나라도 존재하면 종양이 있다고 판단한다.

정상적인 혈관의 예시 1 :

정상적인 혈관의 예시 2 :

종양의 예시:

위 경우는 너비가 2이고 길이가 3인 직사각형이 있기 때문에 종양이라고 판단한다.

아코를 위해! 그리고 동국인들의 혈관 건강을 위해! 프로그램을 만들어주자.

입력

첫째 줄에는 X-ray 사진의 세로길이 $N$과 가로길이 $M$이 주어진다. $(2\leq N, M \leq 1,000円)$

다음 $N$개의 줄에 길이 $M$의 0ドル$과 1ドル$로 이루어진 문자열로 이루어진 X-ray 사진이 주어진다.

출력

종양이 있다면 1ドル$을 출력하고, 종양이 없다면 0ドル$을 출력한다.

제한

노트

동국대학교 일산병원은 고양시에 있으며, 동국대학교의 재학생이라면 누구든 할인을 받을 수 있다.