직사각형 방어막이 \(M \times N\)개의 칸으로 나뉘어 있다. 방어막의 위쪽은 바깥쪽이고 아래쪽은 안쪽이다.

각 칸은 통과할 수 있는 칸 또는 막힌 칸이다. 외부에서 방어막의 맨 윗줄에 있는 모든 통과 가능한 칸으로 물질을 흘려보낸다. 물질은 현재 칸과 변을 공유하는 위쪽, 아래쪽, 왼쪽, 오른쪽의 통과 가능한 칸으로 이동할 수 있다. 모서리만 맞닿은 칸으로는 이동할 수 없다.

물질이 맨 아랫줄의 칸 하나 이상에 도달할 수 있다면 방어막을 침투할 수 있다. 주어진 방어막을 바깥쪽에서 안쪽까지 침투할 수 있는지 판정하여라.

입력

첫째 줄에 방어막의 행 수 \(M\)과 열 수 \(N\)이 공백으로 구분되어 주어진다.

다음 \(M\)개의 줄에 길이가 \(N\)인 문자열이 주어진다. 0은 통과할 수 있는 칸, 1은 막힌 칸을 나타낸다.

출력

바깥쪽에서 안쪽까지 침투할 수 있다면 YES를, 그렇지 않다면 NO를 출력한다.

제한

• \(2 \le M, N \le 1,000\)

예제 입력 1

5 6
010101
010000
011101
100011
001011

예제 출력 1

NO

맨 윗줄의 통과 가능한 칸에서 출발해 이동할 수 있는 영역은 모두 맨 아랫줄에 도달하기 전에 막힌다. 따라서 방어막을 침투할 수 없다.

예제 입력 2

8 8
11000111
01100000
00011001
11001000
10001001
10111100
01010000
00001011

예제 출력 2

YES

예를 들어 행과 열을 위쪽과 왼쪽부터 \(1\)씩 세었을 때,

\((1,5) \rightarrow (2,5) \rightarrow (2,6) \rightarrow (3,6) \rightarrow (4,6) \rightarrow (5,6) \rightarrow (5,7) \rightarrow (6,7) \rightarrow (7,7) \rightarrow (7,6) \rightarrow (8,6)\)

순서로 통과 가능한 칸을 따라 이동할 수 있다. 맨 윗줄에서 맨 아랫줄까지 도달할 수 있으므로 방어막을 침투할 수 있다.