카드 섞기

면접 대비

시간 제한2초메모리 제한512 MB

요약

위에서부터 번호가 매겨진 카드 더미에 두 종류의 섞기 동작을 순서대로 적용한 뒤 k-1, k, k+1 위치의 카드를 구합니다.

난이도: 보통10점 중 4점
유형: 시뮬레이션, 큐
정답자: 아직 제출이 없습니다

문제

앨리스는 새로 문을 연 ResortWorld 카지노에서 포커 테이블 딜러로 일한다. 덱을 섞을 때는 유별나게도 다음 두 가지 방법으로만 카드를 옮긴다.

A: 맨 위 카드를 빼서 맨 아래에 놓는다.
B: 위에서 두 번째 카드를 빼서 맨 아래에 놓는다.

앨리스가 처음에 들고 있는 카드는 $m$ 장이다. $m$ 은 보통 덱의 52장보다 훨씬 클 수도 있다. 카드에는 위에서부터 차례로 번호가 붙어 있어서 맨 위 카드가 $0$ 번, 맨 아래 카드가 $m-1$ 번이다.

동작 순서가 ABBABA이면 덱은 다음과 같이 바뀐다.

적용한 동작	위에서 아래로 본 덱
시작	0 1 2 3 4 5
`A`	1 2 3 4 5 0
`B`	1 3 4 5 0 2
`B`	1 4 5 0 2 3
`A`	4 5 0 2 3 1
`B`	4 0 2 3 1 5
`A`	0 2 3 1 5 4

동작을 모두 적용한 뒤, 맨 위에서 세어 $k-1$ 번째, $k$ 번째, $k+1$ 번째 자리에 놓인 카드의 번호를 구하는 프로그램을 작성하시오. 맨 위 카드를 $0$ 번째로 센다.

입력

한 줄에 $m$ , $k$ , 동작 순서가 공백으로 구분되어 주어진다. $m$ 은 3 이상 1,000,000 이하이고, $k$ 는 $0 < k < m-1$ 을 만족한다. 동작 순서는 A와 B로만 이루어지며 길이는 1 이상 100,000 이하다. 입력의 마지막 문자는 마침표 .이고, 입력이 끝났다는 표시다.

출력

동작을 모두 적용한 뒤 맨 위에서 $k-1$ 번째, $k$ 번째, $k+1$ 번째 카드의 번호를 공백 하나로 구분해 한 줄에 출력한다.

예제1

예제 1
입력
```
6 3 ABBABA.
```
예상 출력
```
3 1 5
```