별 가두기
면접 대비시간 제한1초메모리 제한512 MB
첫 번째 열의 한 칸에서 시작한 별이 오른쪽으로 이동하며 시계 방향으로 돌 때, 영원히 격자 안에 갇히는 행의 개수와 번호를 구한다.
문제
스타는 별을 가두는 장치를 만들어 본인이 가지고 있는 별을 보관하려고 한다.
스타의 장치에는 크기의 격자가 있으며, 격자의 각 칸에는 양의 정수가 적혀 있다. 이 장치는 다음과 같은 과정을 거쳐 격자에 별을 가둔다.
-
첫 번째 열의 원하는 칸에 별을 올려둔다.
-
다음과 같은 과정을 따라 별이 이동한다.
- 별은 바라보고 있는 방향으로, 별이 놓인 칸에 적힌 수만큼 이동한다.
- 별이 바라보는 방향이 시계 방향으로 90도 돌아간다.
별은 처음에 오른쪽을 바라보고 있으며, 별이 격자 밖으로 나가지 않고 위 과정이 무한히 반복된다면 별을 성공적으로 가둔 것이다. 하지만 중간에 별이 격자 밖으로 나가게 된다면 별을 가두는 데에 실패한 것이다.

스타는 처음에 별을 어느 칸에 올려놔야 별을 가둘 수 있는지 궁금해졌다. 스타를 위해 별을 가둘 수 있는 칸을 알아 내보자.
입력
첫째 줄에 장치의 세로 길이 과 가로 길이 이 주어진다. 은 정수이다.
둘째 줄부터 개의 줄에 걸쳐 격자에 적힌 값이 공백을 사이에 두고 주어진다. 격자에 적힌 값은 이상 이하의 정수이다.
출력
첫째 줄에는 별을 가두기 위해 처음에 올려둘 수 있는 칸의 개수를 출력한다.
둘째 줄에는 별을 가두기 위해 처음에 올려둘 수 있는 칸들이 몇 번째 행에 있는지 공백을 사이에 두고 오름차순으로 출력한다. 그러한 칸이 존재하지 않으면 출력하지 않는다.