시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB71120.000%

문제

왼쪽에서 오른쪽으로 늘어선 N개의 열린 박스들이 있다. 각각의 박스에는 정확하게 두개의 공이 있다. 그리고 각각의 공은 흰색 또는 검은색이다.

첫 번째(가장 왼쪽) 박스 위에 크레인이 있다. 그리고 우리는 다음 커맨드를 통해 크레인을 조작할 수 있다.

  • LIJEVO: 크레인을 왼쪽 박스로 옮긴다
  • DESNO: 크레인을 오른쪽 박스로 옮긴다
  • UZMI BIJELU: 아래의 박스로부터 흰색 공을 꺼낸다
  • UZMI CRNU: 아래의 박스로부터 검은색 공을 꺼낸다
  • SPUSTI BIJELU: 아래의 박스에 흰색 공을 떨어뜨린다
  • SPUSTI CRNU: 아래의 박스에 검은색 공을 떨어뜨린다

크레인은 공 두개 까지만 들 수 있다. 반면 각각의 박스에 넣을 수 있는 공의 수에는 제한이 없다.

우리는 다음 조건들이 만족되었을때 공이 "정렬되었다"라고 말한다.

  • 각각의 박스에는 같은색의 공이 정확히 두개씩 있다
  • 흰색 공으로 채워진 어떤 두 박스 사이에 검은색 공으로 채워진 박스는 존재하지 않는다
  • 검은색 공으로 채워진 어떤 두 박스 사이에 흰색 공으로 채워진 박스는 존재하지 않는다

위의 조건을 만족시키도록하는 커맨드의 최소 절차를 찾는 프로그램을 작성하라.

당신의 답에 있는 각각의 커맨드는 유효해야한다(크레인은 가장 왼쪽 박스로부터 왼쪽으로 갈 수없다, 크레인은 2개를 넘는 공을 들어서는 안 된다, 등등...).

입력

입력의 첫 번째 줄에는 정수 N이 주어진다, 2 ≤ N ≤ 500.

두 번째 줄에는 N개의 각 박스에 포함된 내용물을 나타내는 이니셜이 차례대로 주어진다.

각 박스에는 'B' 또는 'C'인 두개의 문자가 있다. 문자 'B'는 흰색 공을 나타내고 문자 'C'는 검은색 공을 나타낸다.

출력

각 줄에 하나씩, 모든 커맨드를 출력하라.

테스트 데이터는 유일하진 않더라도, 항상 해법이 존재한다.

예제 입력 1

3
CC BC BC

예제 출력 1

DESNO
UZMI BIJELU
DESNO
SPUSTI BIJELU
UZMI CRNU
LIJEVO
SPUSTI CRNU

예제 입력 2

5
BC BB CB BB CC

예제 출력 2

UZMI CRNU
DESNO
DESNO
UZMI CRNU
DESNO
SPUSTI CRNU
UZMI BIJELU
SPUSTI CRNU
UZMI BIJELU
LIJEVO
SPUSTI BIJELU
LIJEVO
LIJEVO
SPUSTI BIJELU

예제 입력 3

7
BB BC CC CC CC BC BB

예제 출력 3

UZMI BIJELU
UZMI BIJELU
DESNO
DESNO
DESNO
DESNO
SPUSTI BIJELU
SPUSTI BIJELU
UZMI CRNU
UZMI CRNU
LIJEVO
LIJEVO
LIJEVO
LIJEVO
SPUSTI CRNU
SPUSTI CRNU
DESNO
UZMI BIJELU
DESNO
DESNO
DESNO
DESNO
SPUSTI BIJELU
UZMI CRNU
LIJEVO
LIJEVO
LIJEVO
LIJEVO
SPUSTI CRNU
W3sicHJvYmxlbV9pZCI6IjMxNzEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQwNmNcdWI4MDhcdWM3NzgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzY3Y1x1Y2FiZFx1YzVkMFx1YzExYyBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3M2NcdWI4NWMgXHViMjk4XHVjNWI0XHVjMTIwIE5cdWFjMWNcdWM3NTggXHVjNWY0XHViOWIwIFx1YmMxNVx1YzJhNFx1YjRlNFx1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWJjMTVcdWMyYTRcdWM1ZDBcdWIyOTQgXHVjODE1XHVkNjU1XHVkNTU4XHVhYzhjIFx1YjQ1MFx1YWMxY1x1Yzc1OCBcdWFjZjVcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YWNmNVx1Yzc0MCBcdWQ3NzBcdWMwYzkgXHViNjEwXHViMjk0IFx1YWM4MFx1Yzc0MFx1YzBjOVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjY2FiIFx1YmM4OFx1YzlmOChcdWFjMDBcdWM3YTUgXHVjNjdjXHVjYWJkKSBcdWJjMTVcdWMyYTQgXHVjNzA0XHVjNWQwIFx1ZDA2Y1x1YjgwOFx1Yzc3OFx1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWM2YjBcdWI5YWNcdWIyOTQgXHViMmU0XHVjNzRjIFx1Y2VlNFx1YjllOFx1YjRkY1x1Yjk3YyBcdWQxYjVcdWQ1NzQgXHVkMDZjXHViODA4XHVjNzc4XHVjNzQ0IFx1Yzg3MFx1Yzc5MVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPkxJSkVWTzogXHVkMDZjXHViODA4XHVjNzc4XHVjNzQ0IFx1YzY3Y1x1Y2FiZCBcdWJjMTVcdWMyYTRcdWI4NWMgXHVjNjJlXHVhZTM0XHViMmU0PFwvbGk+XHJcblx0PGxpPkRFU05POiBcdWQwNmNcdWI4MDhcdWM3NzhcdWM3NDQgXHVjNjI0XHViOTc4XHVjYWJkIFx1YmMxNVx1YzJhNFx1Yjg1YyBcdWM2MmVcdWFlMzRcdWIyZTQ8XC9saT5cclxuXHQ8bGk+VVpNSSBCSUpFTFU6IFx1YzU0NFx1Yjc5OFx1Yzc1OCBcdWJjMTVcdWMyYTRcdWI4NWNcdWJkODBcdWQxMzAgXHVkNzcwXHVjMGM5IFx1YWNmNVx1Yzc0NCBcdWFlYmNcdWIwYjhcdWIyZTQ8XC9saT5cclxuXHQ8bGk+VVpNSSBDUk5VOiBcdWM1NDRcdWI3OThcdWM3NTggXHViYzE1XHVjMmE0XHViODVjXHViZDgwXHVkMTMwIFx1YWM4MFx1Yzc0MFx1YzBjOSBcdWFjZjVcdWM3NDQgXHVhZWJjXHViMGI4XHViMmU0PFwvbGk+XHJcblx0PGxpPlNQVVNUSSBCSUpFTFU6IFx1YzU0NFx1Yjc5OFx1Yzc1OCBcdWJjMTVcdWMyYTRcdWM1ZDAgXHVkNzcwXHVjMGM5IFx1YWNmNVx1Yzc0NCBcdWI1YThcdWM1YjRcdWI3MjhcdWI5YjBcdWIyZTQ8XC9saT5cclxuXHQ8bGk+U1BVU1RJIENSTlU6IFx1YzU0NFx1Yjc5OFx1Yzc1OCBcdWJjMTVcdWMyYTRcdWM1ZDAgXHVhYzgwXHVjNzQwXHVjMGM5IFx1YWNmNVx1Yzc0NCBcdWI1YThcdWM1YjRcdWI3MjhcdWI5YjBcdWIyZTQ8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWQwNmNcdWI4MDhcdWM3NzhcdWM3NDAgXHVhY2Y1IFx1YjQ1MFx1YWMxYyBcdWFlNGNcdWM5YzBcdWI5Y2MgXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YmMxOFx1YmE3NCBcdWFjMDFcdWFjMDFcdWM3NTggXHViYzE1XHVjMmE0XHVjNWQwIFx1YjEyM1x1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWNmNVx1Yzc1OCBcdWMyMThcdWM1ZDBcdWIyOTQgXHVjODFjXHVkNTVjXHVjNzc0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNmIwXHViOWFjXHViMjk0IFx1YjJlNFx1Yzc0YyBcdWM4NzBcdWFjNzRcdWI0ZTRcdWM3NzQgXHViOWNjXHVjODcxXHViNDE4XHVjNWM4XHVjNzQ0XHViNTRjIFx1YWNmNVx1Yzc3NCAmcXVvdDtcdWM4MTVcdWI4MmNcdWI0MThcdWM1YzhcdWIyZTQmcXVvdDtcdWI3N2NcdWFjZTAgXHViOWQwXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWJjMTVcdWMyYTRcdWM1ZDBcdWIyOTQgXHVhYzE5XHVjNzQwXHVjMGM5XHVjNzU4IFx1YWNmNVx1Yzc3NCBcdWM4MTVcdWQ2NTVcdWQ3ODggXHViNDUwXHVhYzFjXHVjNTI5IFx1Yzc4OFx1YjJlNDxcL2xpPlxyXG5cdDxsaT5cdWQ3NzBcdWMwYzkgXHVhY2Y1XHVjNzNjXHViODVjIFx1Y2M0NFx1YzZjY1x1YzljNCBcdWM1YjRcdWI1YTQgXHViNDUwIFx1YmMxNVx1YzJhNCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHVhYzgwXHVjNzQwXHVjMGM5IFx1YWNmNVx1YzczY1x1Yjg1YyBcdWNjNDRcdWM2Y2NcdWM5YzQgXHViYzE1XHVjMmE0XHViMjk0IFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQ8XC9saT5cclxuXHQ8bGk+XHVhYzgwXHVjNzQwXHVjMGM5IFx1YWNmNVx1YzczY1x1Yjg1YyBcdWNjNDRcdWM2Y2NcdWM5YzQgXHVjNWI0XHViNWE0IFx1YjQ1MCBcdWJjMTVcdWMyYTQgXHVjMGFjXHVjNzc0XHVjNWQwIFx1ZDc3MFx1YzBjOSBcdWFjZjVcdWM3M2NcdWI4NWMgXHVjYzQ0XHVjNmNjXHVjOWM0IFx1YmMxNVx1YzJhNFx1YjI5NCBcdWM4NzRcdWM3YWNcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjNzA0XHVjNzU4IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWMyZGNcdWQwYTRcdWIzYzRcdWI4NWRcdWQ1NThcdWIyOTQgXHVjZWU0XHViOWU4XHViNGRjXHVjNzU4IFx1Y2Q1Y1x1YzE4YyBcdWM4MDhcdWNjMjhcdWI5N2MgXHVjYzNlXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWI3N2MuPFwvcD5cclxuXHJcbjxwPlx1YjJmOVx1YzJlMFx1Yzc1OCBcdWIyZjVcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWNlZTRcdWI5ZThcdWI0ZGNcdWIyOTQgXHVjNzIwXHVkNmE4XHVkNTc0XHVjNTdjXHVkNTVjXHViMmU0KFx1ZDA2Y1x1YjgwOFx1Yzc3OFx1Yzc0MCBcdWFjMDBcdWM3YTUgXHVjNjdjXHVjYWJkIFx1YmMxNVx1YzJhNFx1Yjg1Y1x1YmQ4MFx1ZDEzMCBcdWM2N2NcdWNhYmRcdWM3M2NcdWI4NWMgXHVhYzA4IFx1YzIxOFx1YzVjNlx1YjJlNCwgXHVkMDZjXHViODA4XHVjNzc4XHVjNzQwIDJcdWFjMWNcdWI5N2MgXHViMTE4XHViMjk0IFx1YWNmNVx1Yzc0NCBcdWI0ZTRcdWM1YjRcdWMxMWNcdWIyOTQgXHVjNTQ4IFx1YjQxY1x1YjJlNCwgXHViNGYxXHViNGYxLi4uKS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM4MTVcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQsIDIgJmxlOyBOICZsZTsgNTAwLjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBOXHVhYzFjXHVjNzU4IFx1YWMwMSBcdWJjMTVcdWMyYTRcdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDFjIFx1YjBiNFx1YzZhOVx1YmIzY1x1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjNzc0XHViMmM4XHVjMTVjXHVjNzc0IFx1Y2MyOFx1Yjg0MFx1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWJjMTVcdWMyYTRcdWM1ZDBcdWIyOTQgJiMzOTtCJiMzOTsgXHViNjEwXHViMjk0ICYjMzk7QyYjMzk7XHVjNzc4IFx1YjQ1MFx1YWMxY1x1Yzc1OCBcdWJiMzhcdWM3OTBcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWJiMzhcdWM3OTAgJiMzOTtCJiMzOTtcdWIyOTQgXHVkNzcwXHVjMGM5IFx1YWNmNVx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWFjZTAgXHViYjM4XHVjNzkwICYjMzk7QyYjMzk7XHViMjk0IFx1YWM4MFx1Yzc0MFx1YzBjOSBcdWFjZjVcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5LCBcdWJhYThcdWI0ZTAgXHVjZWU0XHViOWU4XHViNGRjXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG5cclxuPHA+XHVkMTRjXHVjMmE0XHVkMmI4IFx1YjM3MFx1Yzc3NFx1ZDEzMFx1YjI5NCBcdWM3MjBcdWM3N2NcdWQ1NThcdWM5YzQgXHVjNTRhXHViMzU0XHViNzdjXHViM2M0LCBcdWQ1NmRcdWMwYzEgXHVkNTc0XHViYzk1XHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIzMTcxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoia3V0aWplIiwiZGVzY3JpcHRpb24iOiI8cD5UaGVyZSBhcmUgTiBvcGVuIGJveGVzLCBhcnJhbmdlZCBmcm9tIGxlZnQgdG8gcmlnaHQuIFRoZXJlIGFyZSBleGFjdGx5IHR3byBiYWxscyBpbiBlYWNoIGJveCwgYW5kIGVhY2ggYmFsbCBpcyBlaXRoZXIgd2hpdGUgb3IgYmxhY2suJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZXJlIGlzIGEgY3JhbmUgYWJvdmUgdGhlIGZpcnN0IChsZWZ0bW9zdCkgYm94IGFuZCB3ZSBjYW4gb3BlcmF0ZSB0aGUgY3JhbmUgd2l0aCB0aGUgZm9sbG93aW5nIGNvbW1hbmRzOiZuYnNwOzxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPkxJSkVWTzogbW92ZSB0aGUgY3JhbmUgb25lIGJveCB0byB0aGUgbGVmdCZuYnNwOzxcL2xpPlxyXG5cdDxsaT5ERVNOTzogbW92ZSB0aGUgY3JhbmUgb25lIGJveCB0byB0aGUgcmlnaHQmbmJzcDs8XC9saT5cclxuXHQ8bGk+VVpNSSBCSUpFTFU6IHRha2UgdGhlIHdoaXRlIGJhbGwgZnJvbSB0aGUgYm94IGJlbG93Jm5ic3A7PFwvbGk+XHJcblx0PGxpPlVaTUkgQ1JOVTogdGFrZSB0aGUgYmxhY2sgYmFsbCBmcm9tIHRoZSBib3ggYmVsb3cmbmJzcDs8XC9saT5cclxuXHQ8bGk+U1BVU1RJIEJJSkVMVTogZHJvcCB0aGUgd2hpdGUgYmFsbCB0byB0aGUgYm94IGJlbG93Jm5ic3A7PFwvbGk+XHJcblx0PGxpPlNQVVNUSSBDUk5VOiBkcm9wIHRoZSBibGFjayBiYWxsIHRvIHRoZSBib3ggYmVsb3cmbmJzcDs8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5UaGUgY3JhbmUgY2FuIGNhcnJ5IG9ubHkgdHdvIGJhbGxzIGF0IHRoZSBzYW1lIHRpbWUsIGJ1dCBpbiBlYWNoIGJveCB3ZSBjYW4gcHV0IGFuIHVubGltaXRlZCBudW1iZXIgb2YgYmFsbHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldlIHNheSB0aGF0IHRoZSBiYWxscyBhcmUgJnF1b3Q7YXJyYW5nZWQmcXVvdDsgaWYgYWxsIG9mIHRoZSBmb2xsb3dpbmcgc3RhdGVtZW50cyBhcmUgc2F0aXNmaWVkOiZuYnNwOzxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPnRoZXJlIGFyZSBleGFjdGx5IHR3byBiYWxscyBpbiBlYWNoIGJveCBhbmQgdGhleSBoYXZlIHRoZSBzYW1lIGNvbG9yJm5ic3A7PFwvbGk+XHJcblx0PGxpPnRoZXJlIGlzIG5vIGJveCB3aXRoIGJsYWNrIGJhbGxzIGJldHdlZW4gYW55IHR3byBib3hlcyB3aXRoIHdoaXRlIGJhbGxzJm5ic3A7PFwvbGk+XHJcblx0PGxpPnRoZXJlIGlzIG5vIGJveCB3aXRoIHdoaXRlIGJhbGxzIGJldHdlZW4gYW55IHR3byBib3hlcyB3aXRoIGJsYWNrIGJhbGxzJm5ic3A7PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgd2lsbCBmaW5kIHNvbWUgc21hbGxlc3Qgc2VxdWVuY2Ugb2YgY29tbWFuZHMgdGhhdCB3aWxsIGFycmFuZ2UgdGhlIGJhbGxzIHNvIHRoYXQgdGhlIGFib3ZlIHJ1bGVzIGFyZSBzYXRpc2ZpZWQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggY29tbWFuZCBpbiB5b3VyIHNvbHV0aW9uIG11c3QgYmUgdmFsaWQgKHRoZSBjcmFuZSBtdXN0IG5vdCBnbyBsZWZ0IGZyb20gdGhlIGxlZnRtb3N0IGJveCwgaXQgbXVzdCBub3QgY2FycnkgbW9yZSB0aGVuIHR3byBiYWxscywgZXRjLi4uKS4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGFuIGludGVnZXIgTiwgMiAmbGU7IE4gJmxlOyA1MDAuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBjb250YWlucyBhIHNlcXVlbmNlIG9mIE4gbGV0dGVycyAmbmRhc2g7IHRoZSBpbml0aWFsIGNvbnRlbnRzIG9mIHRoZSBib3hlcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Rm9yIGVhY2ggYm94IChmcm9tIGxlZnQgdG8gdGhlIHJpZ2h0KSB0aGVyZSBhcmUgdHdvIGxldHRlcnMgJiMzOTtCJiMzOTsgb3IgJiMzOTtDJiMzOTsuIFRoZSBsZXR0ZXIgJiMzOTtCJiMzOTsgcmVwcmVzZW50cyBhIHdoaXRlIGJhbGwgYW5kIHRoZSBsZXR0ZXIgJiMzOTtDJiMzOTsgcmVwcmVzZW50cyBhIGJsYWNrIGJhbGwuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IGFsbCBvZiB0aGUgY29tbWFuZHMsIGVhY2ggb24gaXRzIG93biBsaW5lLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Ob3RlOiB0aGUgdGVzdCBkYXRhIHdpbGwgYmUgc3VjaCB0aGF0IGEgc29sdXRpb24sIGFsdGhvdWdoIG5vdCBuZWNlc3NhcmlseSB1bmlxdWUsIHdpbGwgYWx3YXlzIGV4aXN0LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=