34820번 - 똥 피하기 게임

문제

당신의 친구는 '똥 피하기 게임'이라는 재미있는 게임을 개발하고 있다. 그러던 중, 친구는 당신에게 게임 테스트를 요청하였다. 게임의 규칙은 다음과 같다.

• 게임 화면은 $N \times M$ 크기의 격자이다. 각 칸은 빈 칸이거나, 똥이 놓여 있다. 단, 격자의 맨 아래 행의 칸에는 똥이 놓여 있지 않다.
• 당신의 캐릭터는 처음에 맨 아래 행의 원하는 칸에 위치할 수 있다.
• 1ドル$초가 지날 때마다, 캐릭터와 똥의 이동이 일어난다. 캐릭터는 왼쪽으로 한 칸 이동하거나, 오른쪽으로 한 칸 이동해야 한다. 이동하고자 하는 방향이 격자 바깥이 아닌 경우에만 이동할 수 있으며, 가만히 멈춰 있을 수는 없다.
• 각 똥은 1ドル$초마다 아래로 한 칸씩 떨어진다. 만약 똥이 격자의 맨 아래 행을 벗어나면, 다시 같은 열의 맨 위 행으로 올라간다.
• 만약 어떤 순간에 캐릭터와 똥이 같은 칸에 위치하게 되면, 게임은 즉시 끝난다.
• 각 1ドル$초마다 일어나는 캐릭터와 똥의 이동은 모두 동시에 일어나며, 이동하는 데 걸리는 시간과 이동하는 도중 똥과 캐릭터가 같은 칸에 위치하는 경우는 없다고 가정한다.

똥 피하기 게임의 규칙을 읽어본 당신은 한 가지 허점을 발견했다.

정해진 수의 똥이 격자를 계속해서 순환하며 떨어지기 때문에, 처음 똥의 배치만 알면 똥의 움직임을 완전히 예측할 수 있다는 것이다.

그렇다면, 캐릭터가 특정 칸에서 시작해 적절히 움직여서 영원히 게임이 끝나지 않도록 만들 수 있을지도 모른다.

친구를 놀라게 하기 위해, 초기 격자 상태를 보고 맨 아래 행의 어떤 칸에서 시작하면 영원히 게임을 끝내지 않을 수 있는지 모두 찾아보자!

입력

첫째 줄에 두 정수 $N,ドル $M$이 주어진다. $(N\ge 2;$ $M\ge2;$ $N\times M \le 10^6)$

둘째 줄부터 $N$개의 줄에 걸쳐, $N \times M$ 크기의 초기 격자의 상태가 맨 위 행부터 맨 아래 행까지 순서대로 주어진다.

이때 각 $N$개의 줄은 빈 칸을 나타내는 .와 똥이 있는 칸을 나타내는 X로만 이루어져 있는, 길이가 $M$인 문자열이다.

맨 아래 행의 칸에는 똥이 놓여 있지 않다.

출력

첫째 줄에 조건을 만족하는 맨 아래 행의 칸의 개수 $K$를 출력한다. (0ドル \le K \le M$)

둘째 줄에 그러한 칸들이 왼쪽에서부터 몇 번째 열의 칸인지를 나타내는 $K$개의 정수를, 오름차순으로 공백으로 구분하여 출력한다.

제한

노트