띠 모양의 자물쇠가 있다. 이 자물쇠는 한 줄로 늘어선 N 개의 칸으로 이루어져 있고, 각 칸에는 1부터 N 까지의 숫자가 하나씩 들어 있다.
맨 처음에는 1번째 칸부터 N 번째 칸까지 1부터 N 까지 숫자가 순서대로 하나씩 들어 있다.
아래 그림 1 은 10 개의 칸으로 이루어진 자물쇠의 맨 처음 모양을 보여주고 있다.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
이 자물쇠를 잠그기 위해서는 다음과 같은 3회의 동작을 연속적으로 수행해야 한다.
첫 번째 동작은 왼쪽으로 밀기이다. 칸 밖으로 밀려나간 번호는 다시 오른쪽으로 돌아온다. 그림 1의 자물쇠를 왼쪽으로 3칸 밀고 나면 그림 2와 같게 된다. 이렇게 왼쪽으로 k 칸 밀기 동작을 k -왼쪽밀기라고 부른다. 이때 1 <= k < N이다.
| 4 | 5 | 6 | 7 | 8 | 9 | 10 | 1 | 2 | 3 |
그 다음 동작은 정해진 구간의 숫자를 뒤집는 것이다.
예를 들어 그림 2의 자물쇠에서 7번째 칸에서부터 9번째 칸까지 숫자 <10,1,2>를 뒤집으면 다음 그림 3과 같게 된다. p 번째 칸부터 q 번째 칸까지 숫자들을 뒤집는 동작을 (p,q)-구간뒤집기라고 한다. 이때 항상 p < q 이다.
| 4 | 5 | 6 | 7 | 8 | 9 | 2 | 1 | 10 | 3 |
이 상황에서 다시 5-왼쪽밀기 동작을 수행하였다면 자물쇠 모양은 아래 그림 4와 같게 된다.
| 9 | 2 | 1 | 10 | 3 | 4 | 5 | 6 | 7 | 8 |
위에서 3-왼쪽밀기, (7,9)-구간뒤집기, 다시 5-왼쪽밀기의 동작을 차례로 수행하여 자물쇠를 잠궜다. 잠긴 자물쇠의 마지막 상태를 입력으로 받아서 그렇게 만든 3회의 동작을 찾아내는 프로그램을 작성하시오. 예를 들어 자물쇠 모양이 그림 4와 같다면 그 답은 3-왼쪽밀기, (7,9)-구간뒤집기, 5-왼쪽밀기이다.
프로그램의 실행시간은 1초를 넘을 수 없다. 부분 점수는 없다.
입력 10 9 2 1 10 3 4 5 6 7 8 출력 3 7 9 5
출처:koi 초등지역기출