#2100 수열

10  2 s   128 MB  

Description

세준이는 가장 처음에 수 하나만 가지고 있는 수열을 가지고 있다. 매 초마다 1은 132로 바뀌고, 2는 211로 바뀌고, 3은 232로 바뀐다. 이런 변환은 매 초마다 동시에 일어난다. N초 후에 Left번째 수부터 Right번째 수 중에 1의 개수, 2의 개수, 3의 개수를 구하는 프로그램을 작성하시오. (Left와 Right를 셀 때, 가장 처음 수를 0번째 수, 그 다음 수를 1번째 수로 센다.)

예를 들어, 가장 처음 수가 1고, N=2이고, Left = 2, Right = 6이라고 하면, 2초 후에는 132232211이 될 것이다. 따라서 Left부터 Right까지 부분 수열은 22322이다. 따라서, 1의 개수는 0, 2의 개수는 4, 3의 개수는 1이다.

Input

첫째 줄에 가장 처음에 들어있던 수가 주어진다. 이 수는 1, 2, 3중에 하나다. 둘째 줄에는 Left가 주어지고, 셋째 줄에는 Right, 넷째 줄에는 N이 주어진다. N은 0보다 크거나 같고, 20보다 작거나 같은 자연수이고, Right는 0보다 크거나 같으며, 3^N-1보다 작거나 같다. Left는 0보다 크거나 같고, Right보다 작거나 같고, Left와 Right는 모두 2147483647보다 작거나 같다.

Output

첫째 줄에 1의 개수, 2의 개수, 3의 개수를 공백으로 구분하여 출력한다.

Sample Input

Sample Output

1
2
6
2
0 4 1

Source

acmicpc.net