한 솔로는 자신의 우주선 밀레니엄 팔콘을 매우 소중하게 여깁니다. 밀레니엄 팔콘의 안전과 경비는 한 솔로에게 매우 중요합니다. 그래서 한 솔로는 그의 우주선이 있는 격납고의 출입구를 지키기 위해 여러 드로이드를 배치했습니다.
격납고의 출입구를 도식적으로 나타내면, 비어 있거나 돌 블록이 배치된 n개의 셀이 일렬로 배열된 형태입니다. 일부 빈 셀에는 드로이드가 서 있습니다. 각 드로이드는 한 솔로가 지정한 이동 알고리즘에 따라 움직입니다. 이동 알고리즘은 각각 왼쪽이나 오른쪽으로 한 셀씩 이동하라는 명령인 L 또는 R로 구성된 m개의 명령으로 이루어져 있습니다. 드로이드들은 동시에 움직이며 다른 드로이드들의 움직임에 영향을 주지 않습니다. 만약 드로이드가 이동 중에 돌 블록이 있는 셀에 위치하게 되면, 드로이드는 충돌하여 파괴되고 더 이상 움직임에 참여하지 않으며, 다른 드로이드들의 움직임을 방해할 수도 없습니다.
한 솔로는 이동 알고리즘을 주의 깊게 작성하지 않았기 때문에, 이 알고리즘을 수행한 결과로 어떤 드로이드가 살아남을지 궁금해졌습니다.
입력
첫 번째 줄에는 두 개의 자연수 n과 m (1 <= n, m <= 10^5)이 주어집니다. 여기서 n은 격납고 출입구의 셀 수를, m은 알고리즘의 길이를 나타냅니다.
두 번째 줄에는 출입구의 구조가 주어집니다: n개의 문자로 구성된 문자열로, 각 문자는 빈 블록을 나타내는 '.', 돌 블록을 나타내는 '#', 드로이드를 나타내는 'D' 중 하나입니다. 출입구의 양 끝(참고: 첫 번째 셀의 이전, 마지막 셀의 이후)에는 돌블록이 있는 것으로 간주할 수 있습니다.
세 번째 줄에는 이동 알고리즘이 주어집니다: m개의 문자로 구성된 문자열로, 각 문자는 왼쪽으로 이동하라는 명령인 L 또는 오른쪽으로 이동하라는 명령인 R입니다.
junisuni08 2년 전 2
한 솔로는 자신의 우주선 밀레니엄 팔콘을 매우 소중하게 여깁니다. 밀레니엄 팔콘의 안전과 경비는 한 솔로에게 매우 중요합니다. 그래서 한 솔로는 그의 우주선이 있는 격납고의 출입구를 지키기 위해 여러 드로이드를 배치했습니다.
격납고의 출입구를 도식적으로 나타내면, 비어 있거나 돌 블록이 배치된 n개의 셀이 일렬로 배열된 형태입니다. 일부 빈 셀에는 드로이드가 서 있습니다. 각 드로이드는 한 솔로가 지정한 이동 알고리즘에 따라 움직입니다. 이동 알고리즘은 각각 왼쪽이나 오른쪽으로 한 셀씩 이동하라는 명령인 L 또는 R로 구성된 m개의 명령으로 이루어져 있습니다. 드로이드들은 동시에 움직이며 다른 드로이드들의 움직임에 영향을 주지 않습니다. 만약 드로이드가 이동 중에 돌 블록이 있는 셀에 위치하게 되면, 드로이드는 충돌하여 파괴되고 더 이상 움직임에 참여하지 않으며, 다른 드로이드들의 움직임을 방해할 수도 없습니다.
한 솔로는 이동 알고리즘을 주의 깊게 작성하지 않았기 때문에, 이 알고리즘을 수행한 결과로 어떤 드로이드가 살아남을지 궁금해졌습니다.
입력
첫 번째 줄에는 두 개의 자연수 n과 m (1 <= n, m <= 10^5)이 주어집니다. 여기서 n은 격납고 출입구의 셀 수를, m은 알고리즘의 길이를 나타냅니다.
두 번째 줄에는 출입구의 구조가 주어집니다: n개의 문자로 구성된 문자열로, 각 문자는 빈 블록을 나타내는 '.', 돌 블록을 나타내는 '#', 드로이드를 나타내는 'D' 중 하나입니다. 출입구의 양 끝(참고: 첫 번째 셀의 이전, 마지막 셀의 이후)에는 돌블록이 있는 것으로 간주할 수 있습니다.
세 번째 줄에는 이동 알고리즘이 주어집니다: m개의 문자로 구성된 문자열로, 각 문자는 왼쪽으로 이동하라는 명령인 L 또는 오른쪽으로 이동하라는 명령인 R입니다.
출력
첫 번째 줄에 알고리즘 실행 결과 살아남을 드로이드의 수 k를 출력합니다.
다음 줄에 살아남을 드로이드의 위치를 오름차순으로 k개의 숫자로 출력합니다.