시간 제한메모리 제한제출정답맞힌 사람정답 비율
7 초 128 MB765056134911.579%

문제

Brainf**k 프로그램이 주어졌을 때, 이 프로그램이 끝나는지, 무한 루프에 빠지는지 알아내는 프로그램을 작성하시오.

무한 루프란, 특정 시점부터 탈출하지 않고 무한히 반복 실행되는 루프를 말한다.

Brainf**k 인터프리터는 정수를 담는 하나의 배열(unsigned 8-bit 정수)과, 그 배열의 칸 하나를 가리키는 포인터로 이루어져 있다. Brainf**k 프로그램은 다음과 같이 8개의 명령어로 이루어져 있다.

- 포인터가 가리키는 수를 1 감소시킨다. (modulo 28)
+ 포인터가 가리키는 수를 1 증가시킨다. (modulo 28)
< 포인터를 왼쪽으로 한 칸 움직인다.
> 포인터를 오른쪽으로 한 칸 움직인다.
[ 만약 포인터가 가리키는 수가 0이라면, [ 와 짝을 이루는 ] 의 다음 명령으로 점프한다.
] 만약 포인터가 가리키는 수가 0이 아니라면, ] 와 짝을 이루는 [ 의 다음 명령으로 점프한다.
. 포인터가 가리키는 수를 출력한다.
, 문자 하나를 읽고 포인터가 가리키는 곳에 저장한다. 입력의 마지막(EOF)인 경우에는 255를 저장한다.

인터프리터는 Brainf**k 프로그램의 첫 번째 명령부터 수행하고, 더이상 수행할 명령이 없다면, 프로그램을 종료한다. 각 명령을 수행하고 나면, 다음 명령을 수행한다. 물론 [이나 ]인 경우에는 다음 명령으로 이동하는 것이 아니라 점프를 한다.

데이터 배열의 크기는 문제에서 주어지는 값을 사용해야 한다. 또, 데이터 배열의 값이 underflow나 overflow를 일으켰을 때는 일반적인 방법을 따르면 된다. 프로그램을 수행하기 전에, 데이터 배열의 값은 0으로 초기화되어 있고, 포인터가 가리키는 칸은 0번 칸이다.

포인터를 왼쪽이나 오른쪽으로 움직일 때, 데이터 배열의 범위를 넘어간다면, 반대쪽으로 넘어가게 된다. 즉, 포인터가 0을 가리킬 때, 1을 감소시킨다면, 배열의 크기 - 1번째를 가리키게 된다.

[]는 루프를 의미하며, 중첩될 수 있다. 입력으로 주어진 프로그램은 잘 짜여 있음이 보장된다. 즉 프로그램을 왼쪽에서 오른쪽으로 훑으면서 [의 개수에서 ]의 개수를 빼면 항상 0보다 크거나 같고, 맨 끝까지 훑으면 그 값은 0이 된다.

이 문제는 Brainf**k 프로그램이 무한 루프에 빠지는지 안 빠지는지를 검사하기만 하면 된다. 따라서, 출력은 무시한다.

입력

첫째 줄에 테스트 케이스의 개수 t (0 < t ≤ 20)가 주어진다. 각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 sm, sc, si가 주어진다. sm은 메모리(배열)의 크기이고, sc는 프로그램 코드의 크기, si는 입력의 크기이다. (0 < sm ≤ 100,000, 0 < sc, si < 4096)

둘째 줄에는 Brainf**k 프로그램이 주어진다. 프로그램은 sc개의 문자로 이루어져 있다.

셋째 줄에는 프로그램의 입력이 주어진다. (공백이 아니면서 출력할 수 있는 문자만 주어진다)

출력

각 테스트 케이스에 대해서, 프로그램이 종료된다면 "Terminates"를, 무한 루프에 빠지게 된다면 "Loops"를 출력한다. 무한 루프에 빠졌을 때는, 프로그램의 어느 부분이 무한 루프인지를 출력한다. ([]의 위치) 프로그램이 명령어를 50,000,000번 이상 수행한 경우, 프로그램은 항상 종료되었거나 무한 루프에 빠져있다. 무한 루프일 경우, 해당 루프는 적어도 한 번 실행이 완료된 상태이며, 한 번의 무한 루프에서 실행되는 명령어의 개수는 50,000,000개 이하이다.

예제 입력 1

4
10 4 3
+-.,
qwe
1000 5 1
+[+-]
a
100 74 4
+++++[->++<]>[-<+++++++>]<[->+>+>+>+<<<<]>+++>--->++++++++++>---<<<.>.>.>.
xxyz
9999 52 14
+++++[>+++++++++<-],+[-[>--.++>+<<-]>+.->[<.>-]<<,+]
this_is_a_test

예제 출력 1

Terminates
Loops 1 4
Terminates
Terminates
W3sicHJvYmxlbV9pZCI6IjM5NTQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJCcmFpbmYqKmsgXHVjNzc4XHVkMTMwXHVkNTA0XHViOWFjXHVkMTMwIiwiZGVzY3JpcHRpb24iOiI8cD5CcmFpbmYqKmsgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1Yzc3NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NzQgXHViMDVkXHViMDk4XHViMjk0XHVjOWMwLCBcdWJiMzRcdWQ1NWMgXHViOGU4XHVkNTA0XHVjNWQwIFx1YmU2MFx1YzljMFx1YjI5NFx1YzljMCBcdWM1NGNcdWM1NDRcdWIwYjRcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XHViYjM0XHVkNTVjIFx1YjhlOFx1ZDUwNFx1Yjc4MCwgXHVkMmI5XHVjODE1IFx1YzJkY1x1YzgxMFx1YmQ4MFx1ZDEzMCBcdWQwYzhcdWNkOWNcdWQ1NThcdWM5YzAgXHVjNTRhXHVhY2UwIFx1YmIzNFx1ZDU1Y1x1ZDc4OCBcdWJjMThcdWJjZjUgXHVjMmU0XHVkNTg5XHViNDE4XHViMjk0IFx1YjhlOFx1ZDUwNFx1Yjk3YyBcdWI5ZDBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPkJyYWluZioqayBcdWM3NzhcdWQxMzBcdWQ1MDRcdWI5YWNcdWQxMzBcdWIyOTQgXHVjODE1XHVjMjE4XHViOTdjIFx1YjJmNFx1YjI5NCBcdWQ1NThcdWIwOThcdWM3NTggXHViYzMwXHVjNWY0KHVuc2lnbmVkIDgtYml0IFx1YzgxNVx1YzIxOClcdWFjZmMsIFx1YWRmOCBcdWJjMzBcdWM1ZjRcdWM3NTggXHVjZTc4IFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWFjMDBcdWI5YWNcdWQwYTRcdWIyOTQgXHVkM2VjXHVjNzc4XHVkMTMwXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIEJyYWluZioqayBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCA4XHVhYzFjXHVjNzU4IFx1YmE4NVx1YjgzOVx1YzViNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48dGFibGUgY2xhc3M9XCJ0YWJsZSB0YWJsZS1ib3JkZXJlZFwiIHN0eWxlPVwid2lkdGg6MTAwJVwiPlxyXG5cdDx0Ym9keT5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoIHN0eWxlPVwid2lkdGg6MjAlXCI+PGNvZGU+LTxcL2NvZGU+PFwvdGg+XHJcblx0XHRcdDx0ZCBzdHlsZT1cIndpZHRoOjgwJVwiPlx1ZDNlY1x1Yzc3OFx1ZDEzMFx1YWMwMCBcdWFjMDBcdWI5YWNcdWQwYTRcdWIyOTQgXHVjMjE4XHViOTdjIDEgXHVhYzEwXHVjMThjXHVjMmRjXHVkMGE4XHViMmU0LiAobW9kdWxvIDI8c3VwPjg8XC9zdXA+KTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD48Y29kZT4rPFwvY29kZT48XC90aD5cclxuXHRcdFx0PHRkPlx1ZDNlY1x1Yzc3OFx1ZDEzMFx1YWMwMCBcdWFjMDBcdWI5YWNcdWQwYTRcdWIyOTQgXHVjMjE4XHViOTdjIDEgXHVjOTlkXHVhYzAwXHVjMmRjXHVkMGE4XHViMmU0LiAobW9kdWxvIDI8c3VwPjg8XC9zdXA+KTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD48Y29kZT4mbHQ7PFwvY29kZT48XC90aD5cclxuXHRcdFx0PHRkPlx1ZDNlY1x1Yzc3OFx1ZDEzMFx1Yjk3YyBcdWM2N2NcdWNhYmRcdWM3M2NcdWI4NWMgXHVkNTVjIFx1Y2U3OCBcdWM2YzBcdWM5YzFcdWM3NzhcdWIyZTQuPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoPjxjb2RlPiZndDs8XC9jb2RlPjxcL3RoPlxyXG5cdFx0XHQ8dGQ+XHVkM2VjXHVjNzc4XHVkMTMwXHViOTdjIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzczY1x1Yjg1YyBcdWQ1NWMgXHVjZTc4IFx1YzZjMFx1YzljMVx1Yzc3OFx1YjJlNC48XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGg+PGNvZGU+WzxcL2NvZGU+PFwvdGg+XHJcblx0XHRcdDx0ZD5cdWI5Y2NcdWM1N2QgXHVkM2VjXHVjNzc4XHVkMTMwXHVhYzAwIFx1YWMwMFx1YjlhY1x1ZDBhNFx1YjI5NCBcdWMyMThcdWFjMDAgMFx1Yzc3NFx1Yjc3Y1x1YmE3NCwmbmJzcDs8Y29kZSBkYXRhLXN0cmluZ2lmeS10eXBlPVwiY29kZVwiPls8XC9jb2RlPiZuYnNwO1x1YzY0MCBcdWM5ZGRcdWM3NDQgXHVjNzc0XHViOGU4XHViMjk0Jm5ic3A7PGNvZGUgZGF0YS1zdHJpbmdpZnktdHlwZT1cImNvZGVcIj5dPFwvY29kZT4mbmJzcDtcdWM3NTggXHViMmU0XHVjNzRjIFx1YmE4NVx1YjgzOVx1YzczY1x1Yjg1YyBcdWM4MTBcdWQ1MDRcdWQ1NWNcdWIyZTQuPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoPjxjb2RlPl08XC9jb2RlPjxcL3RoPlxyXG5cdFx0XHQ8dGQ+XHViOWNjXHVjNTdkIFx1ZDNlY1x1Yzc3OFx1ZDEzMFx1YWMwMCBcdWFjMDBcdWI5YWNcdWQwYTRcdWIyOTQgXHVjMjE4XHVhYzAwIDBcdWM3NzQgXHVjNTQ0XHViMmM4XHViNzdjXHViYTc0LCZuYnNwOzxjb2RlIGRhdGEtc3RyaW5naWZ5LXR5cGU9XCJjb2RlXCI+XTxcL2NvZGU+Jm5ic3A7XHVjNjQwIFx1YzlkZFx1Yzc0NCBcdWM3NzRcdWI4ZThcdWIyOTQmbmJzcDs8Y29kZSBkYXRhLXN0cmluZ2lmeS10eXBlPVwiY29kZVwiPls8XC9jb2RlPiZuYnNwO1x1Yzc1OCBcdWIyZTRcdWM3NGMgXHViYTg1XHViODM5XHVjNzNjXHViODVjIFx1YzgxMFx1ZDUwNFx1ZDU1Y1x1YjJlNC48XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGg+LjxcL3RoPlxyXG5cdFx0XHQ8dGQ+XHVkM2VjXHVjNzc4XHVkMTMwXHVhYzAwIFx1YWMwMFx1YjlhY1x1ZDBhNFx1YjI5NCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD4sPFwvdGg+XHJcblx0XHRcdDx0ZD5cdWJiMzhcdWM3OTAgXHVkNTU4XHViMDk4XHViOTdjIFx1Yzc3ZFx1YWNlMCBcdWQzZWNcdWM3NzhcdWQxMzBcdWFjMDAgXHVhYzAwXHViOWFjXHVkMGE0XHViMjk0IFx1YWNmM1x1YzVkMCBcdWM4MDBcdWM3YTVcdWQ1NWNcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkoRU9GKVx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgMjU1XHViOTdjIFx1YzgwMFx1YzdhNVx1ZDU1Y1x1YjJlNC48XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3Rib2R5PlxyXG48XC90YWJsZT5cclxuXHJcbjxwPlx1Yzc3OFx1ZDEzMFx1ZDUwNFx1YjlhY1x1ZDEzMFx1YjI5NCBCcmFpbmYqKmsgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzU4IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHViYTg1XHViODM5XHViZDgwXHVkMTMwIFx1YzIxOFx1ZDU4OVx1ZDU1OFx1YWNlMCwgXHViMzU0XHVjNzc0XHVjMGMxIFx1YzIxOFx1ZDU4OVx1ZDU2MCBcdWJhODVcdWI4MzlcdWM3NzQgXHVjNWM2XHViMmU0XHViYTc0LCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjODg1XHViOGNjXHVkNTVjXHViMmU0LiBcdWFjMDEgXHViYTg1XHViODM5XHVjNzQ0IFx1YzIxOFx1ZDU4OVx1ZDU1OFx1YWNlMCBcdWIwOThcdWJhNzQsIFx1YjJlNFx1Yzc0YyBcdWJhODVcdWI4MzlcdWM3NDQgXHVjMjE4XHVkNTg5XHVkNTVjXHViMmU0LiZuYnNwO1x1YmIzY1x1Yjg2MCA8Y29kZT5bPFwvY29kZT5cdWM3NzRcdWIwOTggPGNvZGU+XTxcL2NvZGU+XHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWIyZTRcdWM3NGMgXHViYTg1XHViODM5XHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzQgXHVjNTQ0XHViMmM4XHViNzdjIFx1YzgxMFx1ZDUwNFx1Yjk3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjM3MFx1Yzc3NFx1ZDEzMCBcdWJjMzBcdWM1ZjRcdWM3NTggXHVkMDZjXHVhZTMwXHViMjk0IFx1YmIzOFx1YzgxY1x1YzVkMFx1YzExYyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHVhYzEyXHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YjYxMCwgXHViMzcwXHVjNzc0XHVkMTMwIFx1YmMzMFx1YzVmNFx1Yzc1OCBcdWFjMTJcdWM3NzQgdW5kZXJmbG93XHViMDk4IG92ZXJmbG93XHViOTdjIFx1Yzc3Y1x1YzczY1x1Y2YzMFx1Yzc0NCBcdWI1NGNcdWIyOTQgXHVjNzdjXHViYzE4XHVjODAxXHVjNzc4IFx1YmMyOVx1YmM5NVx1Yzc0NCBcdWI1MzBcdWI5NzRcdWJhNzQgXHViNDFjXHViMmU0LiBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjMjE4XHVkNTg5XHVkNTU4XHVhZTMwIFx1YzgwNFx1YzVkMCwgXHViMzcwXHVjNzc0XHVkMTMwIFx1YmMzMFx1YzVmNFx1Yzc1OCBcdWFjMTJcdWM3NDAgMFx1YzczY1x1Yjg1YyBcdWNkMDhcdWFlMzBcdWQ2NTRcdWI0MThcdWM1YjQgXHVjNzg4XHVhY2UwLCBcdWQzZWNcdWM3NzhcdWQxMzBcdWFjMDAgXHVhYzAwXHViOWFjXHVkMGE0XHViMjk0IFx1Y2U3OFx1Yzc0MCAwXHViYzg4IFx1Y2U3OFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkM2VjXHVjNzc4XHVkMTMwXHViOTdjIFx1YzY3Y1x1Y2FiZFx1Yzc3NFx1YjA5OCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3M2NcdWI4NWMgXHVjNmMwXHVjOWMxXHVjNzdjIFx1YjU0YywgXHViMzcwXHVjNzc0XHVkMTMwIFx1YmMzMFx1YzVmNFx1Yzc1OCBcdWJjOTRcdWM3MDRcdWI5N2MgXHViMTE4XHVjNWI0XHVhYzA0XHViMmU0XHViYTc0LCBcdWJjMThcdWIzMDBcdWNhYmRcdWM3M2NcdWI4NWMgXHViMTE4XHVjNWI0XHVhYzAwXHVhYzhjIFx1YjQxY1x1YjJlNC4gXHVjOTg5LCBcdWQzZWNcdWM3NzhcdWQxMzBcdWFjMDAgMFx1Yzc0NCBcdWFjMDBcdWI5YWNcdWQwYWMgXHViNTRjLCAxXHVjNzQ0IFx1YWMxMFx1YzE4Y1x1YzJkY1x1ZDBhOFx1YjJlNFx1YmE3NCwgXHViYzMwXHVjNWY0XHVjNzU4IFx1ZDA2Y1x1YWUzMCAtIDFcdWJjODhcdWM5ZjhcdWI5N2MgXHVhYzAwXHViOWFjXHVkMGE0XHVhYzhjIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+PGNvZGU+WzxcL2NvZGU+XHVjNjQwIDxjb2RlPl08XC9jb2RlPlx1YjI5NCBcdWI4ZThcdWQ1MDRcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTU4XHViYTcwLCBcdWM5MTFcdWNjYTlcdWI0MjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDAgXHVjNzk4IFx1YzlkY1x1YzVlYyBcdWM3ODhcdWM3NGNcdWM3NzQgXHViY2Y0XHVjN2E1XHViNDFjXHViMmU0LiBcdWM5ODkgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1YzY3Y1x1Y2FiZFx1YzVkMFx1YzExYyBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3M2NcdWI4NWMgXHVkNmQxXHVjNzNjXHViYTc0XHVjMTFjIDxjb2RlPls8XC9jb2RlPlx1Yzc1OCBcdWFjMWNcdWMyMThcdWM1ZDBcdWMxMWMgPGNvZGU+XTxcL2NvZGU+XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWJlN2NcdWJhNzQgXHVkNTZkXHVjMGMxIDBcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgXHViOWU4IFx1YjA1ZFx1YWU0Y1x1YzljMCBcdWQ2ZDFcdWM3M2NcdWJhNzQgXHVhZGY4IFx1YWMxMlx1Yzc0MCAwXHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0IFx1YmIzOFx1YzgxY1x1YjI5NCBCcmFpbmYqKmsgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzc0IFx1YmIzNFx1ZDU1YyBcdWI4ZThcdWQ1MDRcdWM1ZDAgXHViZTYwXHVjOWMwXHViMjk0XHVjOWMwIFx1YzU0OCBcdWJlNjBcdWM5YzBcdWIyOTRcdWM5YzBcdWI5N2MgXHVhYzgwXHVjMGFjXHVkNTU4XHVhZTMwXHViOWNjIFx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHVjZDljXHViODI1XHVjNzQwIFx1YmIzNFx1YzJkY1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggdCAoMCAmbHQ7IHQgJmxlOyAyMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWMxMzggXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgczxzdWI+bTxcL3N1Yj4sIHM8c3ViPmM8XC9zdWI+LCBzPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIHM8c3ViPm08XC9zdWI+XHVjNzQwIFx1YmE1NFx1YmFhOFx1YjlhYyhcdWJjMzBcdWM1ZjQpXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1Yzc3NFx1YWNlMCwgczxzdWI+YzxcL3N1Yj5cdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4IFx1Y2Y1NFx1YjRkY1x1Yzc1OCBcdWQwNmNcdWFlMzAsIHM8c3ViPmk8XC9zdWI+XHViMjk0IFx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWQwNmNcdWFlMzBcdWM3NzRcdWIyZTQuICgwICZsdDsgczxzdWI+bTxcL3N1Yj4gJmxlOyAxMDAsMDAwLCAwICZsdDsgczxzdWI+YzxcL3N1Yj4sIHM8c3ViPmk8XC9zdWI+ICZsdDsgNDA5Nik8XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBCcmFpbmYqKmsgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQwIHM8c3ViPmM8XC9zdWI+XHVhYzFjXHVjNzU4IFx1YmIzOFx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMxNGJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc1OCBcdWM3ODVcdWI4MjVcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoXHVhY2Y1XHViYzMxXHVjNzc0IFx1YzU0NFx1YjJjOFx1YmE3NFx1YzExYyBcdWNkOWNcdWI4MjVcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJiMzhcdWM3OTBcdWI5Y2MgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0KTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzc0IFx1Yzg4NVx1YjhjY1x1YjQxY1x1YjJlNFx1YmE3NCAmcXVvdDtUZXJtaW5hdGVzJnF1b3Q7XHViOTdjLCBcdWJiMzRcdWQ1NWMgXHViOGU4XHVkNTA0XHVjNWQwIFx1YmU2MFx1YzljMFx1YWM4YyBcdWI0MWNcdWIyZTRcdWJhNzQgJnF1b3Q7TG9vcHMmcXVvdDtcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWJiMzRcdWQ1NWMgXHViOGU4XHVkNTA0XHVjNWQwIFx1YmU2MFx1Yzg0Y1x1Yzc0NCBcdWI1NGNcdWIyOTQsIFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc1OCBcdWM1YjRcdWIyOTAgXHViZDgwXHViZDg0XHVjNzc0IFx1YmIzNFx1ZDU1YyBcdWI4ZThcdWQ1MDRcdWM3NzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiAoPGNvZGU+WzxcL2NvZGU+XHVjNjQwIDxjb2RlPl08XC9jb2RlPlx1Yzc1OCBcdWM3MDRcdWNlNTgpIFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc3NCBcdWJhODVcdWI4MzlcdWM1YjRcdWI5N2MgNTAsMDAwLDAwMFx1YmM4OCBcdWM3NzRcdWMwYzEgXHVjMjE4XHVkNTg5XHVkNTVjIFx1YWNiZFx1YzZiMCwgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQwIFx1ZDU2ZFx1YzBjMSBcdWM4ODVcdWI4Y2NcdWI0MThcdWM1YzhcdWFjNzBcdWIwOTggXHViYjM0XHVkNTVjIFx1YjhlOFx1ZDUwNFx1YzVkMCBcdWJlNjBcdWM4MzhcdWM3ODhcdWIyZTQuIFx1YmIzNFx1ZDU1YyBcdWI4ZThcdWQ1MDRcdWM3N2MgXHVhY2JkXHVjNmIwLCBcdWQ1NzRcdWIyZjkgXHViOGU4XHVkNTA0XHViMjk0IFx1YzgwMVx1YzViNFx1YjNjNCBcdWQ1NWMgXHViYzg4IFx1YzJlNFx1ZDU4OVx1Yzc3NCBcdWM2NDRcdWI4Y2NcdWI0MWMgXHVjMGMxXHVkMGRjXHVjNzc0XHViYTcwLCBcdWQ1NWMgXHViYzg4XHVjNzU4IFx1YmIzNFx1ZDU1YyBcdWI4ZThcdWQ1MDRcdWM1ZDBcdWMxMWMgXHVjMmU0XHVkNTg5XHViNDE4XHViMjk0IFx1YmE4NVx1YjgzOVx1YzViNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWIyOTQgNTAsMDAwLDAwMFx1YWMxYyBcdWM3NzRcdWQ1NThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzk1NCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJyYWluRioqa1ZNIiwiZGVzY3JpcHRpb24iOiI8cD5HaXZlbiBhIGJyYWluZioqayBwcm9ncmFtLCBkZXRlcm1pbmUgd2hldGhlciBpdCB0ZXJtaW5hdGVzIG9yIGVudGVycyBhbiBlbmRsZXNzIGxvb3AuPFwvcD5cclxuXHJcbjxwPkEgYnJhaW5mKiprIGludGVycHJldGVyIGhhcyBhIGRhdGEgYXJyYXkgKGNvbnNpc3Rpbmcgb2YgdW5zaWduZWQgOC1iaXQgaW50ZWdlcnMpIHdpdGggYW4gaW5kZXgsIHRoZSBzbyBjYWxsZWQgJnF1b3Q7ZGF0YSBpbmRleCZxdW90OzsgdGhlIGVudHJ5IG9mIHRoZSBhcnJheSBwb2ludGVkIHRvIGJ5IHRoZSBkYXRhIGluZGV4IGlzIHRoZSBzbyBjYWxsZWQgJnF1b3Q7Y3VycmVudCBlbnRyeSZxdW90Oy4gQSBicmFpbmYqKmsgcHJvZ3JhbSBjb25zaXN0cyBvZiBhIHNlcXVlbmNlIG9mIHRoZSBmb2xsb3dpbmcgZWlnaHQgaW5zdHJ1Y3Rpb25zOjxcL3A+XHJcblxyXG48dGFibGUgY2xhc3M9XCJ0YWJsZSB0YWJsZS1ib3JkZXJlZFwiIHN0eWxlPVwid2lkdGg6MTAwJVwiPlxyXG5cdDx0Ym9keT5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoIHN0eWxlPVwid2lkdGg6MjAlXCI+LTxcL3RoPlxyXG5cdFx0XHQ8dGQgc3R5bGU9XCJ3aWR0aDo4MCVcIj5kZWNyZWFzZSBjdXJyZW50IGVudHJ5IGJ5IDEgKG1vZHVsbyAyPHN1cD44PFwvc3VwPik8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGg+KzxcL3RoPlxyXG5cdFx0XHQ8dGQ+aW5jcmVhc2UgY3VycmVudCBlbnRyeSBieSAxIChtb2R1bG8gMjxzdXA+ODxcL3N1cD4pPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoPiZsdDs8XC90aD5cclxuXHRcdFx0PHRkPmRlY3JlYXNlIGRhdGEgaW5kZXggYnkgMTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aD4mZ3Q7PFwvdGg+XHJcblx0XHRcdDx0ZD5pbmNyZWFzZSBkYXRhIGluZGV4IGJ5IDE8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGg+WzxcL3RoPlxyXG5cdFx0XHQ8dGQ+anVtcCBiZWhpbmQgdGhlIG1hdGNoaW5nIF0sIGlmIHRoZSBjdXJyZW50IGVudHJ5IGlzIGVxdWFsIHRvIDA8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGg+XTxcL3RoPlxyXG5cdFx0XHQ8dGQ+anVtcCBiZWhpbmQgdGhlIG1hdGNoaW5nIFsgaWYgdGhlIGN1cnJlbnQgZW50cnkgaXMgbm90IGVxdWFsIHRvIDA8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGg+LjxcL3RoPlxyXG5cdFx0XHQ8dGQ+cHJpbnQgdGhlIGN1cnJlbnQgZW50cnkgYXMgY2hhcmFjdGVyPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRoPiw8XC90aD5cclxuXHRcdFx0PHRkPnJlYWQgYSBjaGFyYWN0ZXIgYW5kIHNhdmUgaXQgaW50byB0aGUgY3VycmVudCBlbnRyeS4gT24gZW5kIG9mIGlucHV0IHNhdmUgMjU1LjxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG5cclxuPHA+SW50ZXJwcmV0YXRpb24gb2YgYSBicmFpbmYqKmsgcHJvZ3JhbSBzdGFydHMgYXQgdGhlIGZpcnN0IGluc3RydWN0aW9uLCBhbmQgdGVybWluYXRlcyBpZiB0aGUgaW5zdHJ1Y3Rpb24gcG9pbnRlciBsZWF2ZXMgdGhlIGVuZCBvZiB0aGUgcHJvZ3JhbS4gQWZ0ZXIgYW4gaW5zdHJ1Y3Rpb24gaXMgZXhlY3V0ZWQsIHRoZSBpbnN0cnVjdGlvbiBwb2ludGVyIGFkdmFuY2VzIHRvIHRoZSBpbnN0cnVjdGlvbiB0byB0aGUgcmlnaHQgKGV4Y2VwdCwgb2YgY291cnNlLCBpZiB0aGUgbG9vcCBpbnN0cnVjdGlvbnMgWyBvciBdIGNhdXNlIGEganVtcCkuPFwvcD5cclxuXHJcbjxwPkluIGFkZGl0aW9uIHRvIHRoZSBwcm9ncmFtLCB5b3Ugd2lsbCBiZSBnaXZlbiB0aGUgc2l6ZSBvZiB0aGUgZGF0YSBhcnJheS4gVGhlIGVudHJpZXMgb2YgdGhlIGRhdGEgYXJyYXkgc2hhbGwgYmUgdW5zaWduZWQgOC1iaXQgaW50ZWdlcnMsIHdpdGggdXN1YWwgb3Zlci0gb3IgdW5kZXJmbG93IGJlaGF2aW91ci4gQXQgdGhlIHN0YXJ0IG9mIHRoZTxcL3A+XHJcblxyXG48cD5wcm9ncmFtLCB0aGUgZGF0YSBhcnJheSBlbnRyaWVzIGFuZCB0aGUgZGF0YSBpbmRleCBzaGFsbCBiZSBpbml0aWFsaXplZCB0byB6ZXJvLiBJbmNyZW1lbnRpbmcgb3IgZGVjcmVtZW50aW5nIHRoZSBkYXRhIGluZGV4IGJleW9uZCB0aGUgYm91bmRhcmllcyBvZiB0aGUgZGF0YSBhcnJheSBzaGFsbCBtYWtlIGl0IHJlLWVudGVyIHRoZSBkYXRhIGFycmF5IGF0IHRoZSBvdGhlciBib3VuZGFyeTsgZS5nLiBkZWNyZW1lbnRpbmcgdGhlIGRhdGEgaW5kZXggd2hlbiBpdCBpcyB6ZXJvIHNoYWxsIHNldCBpdCB0byB0aGUgc2l6ZSBvZiB0aGUgZGF0YSBhcnJheSBtaW51cyBvbmUuPFwvcD5cclxuXHJcbjxwPlRoZSBbIGFuZCBdIGluc3RydWN0aW9ucyBkZWZpbmUgbG9vcHMgYW5kIGFyZSBhbGxvd2VkIHRvIG5lc3QuIEV2ZXJ5IGdpdmVuIHByb2dyYW0gd2lsbCBiZSB3ZWxsZm9ybWVkLCBpLmUuIHdoZW4gdHJhdmVyc2luZyB0aGUgcHJvZ3JhbSBmcm9tIGxlZnQgdG8gcmlnaHQsIHRoZSBudW1iZXIgb2YgWyBpbnN0cnVjdGlvbnMgbWludXMgdGhlIG51bWJlciBvZiBdIGluc3RydWN0aW9ucyB3aWxsIGFsd2F5cyBiZSBncmVhdGVyIG9yIGVxdWFsIHplcm8sIGFuZCBhdCB0aGUgZW5kIG9mIHRoZSBwcm9ncmFtIGl0IHdpbGwgYmUgZXF1YWwgdG8gemVyby48XC9wPlxyXG5cclxuPHA+Rm9yIHRoZSBwdXJwb3NlcyBvZiB0aGUgcHJvYmxlbSwgZGlzY2FyZCB0aGUgb3V0cHV0IG9mIHRoZSBpbnRlcnByZXRlZCBwcm9ncmFtLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IHN0YXJ0cyB3aXRoIGEgbGluZSBjb250YWluaW5nIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyB0ICgwICZsdDsgdCAmbGU7IDIwKS4gRWFjaCB0ZXN0IGNhc2UgY29uc2lzdHMgb2YgdGhyZWUgbGluZXMuIFRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHRocmVlIGludGVnZXJzIHM8c3ViPm08XC9zdWI+LCBzPHN1Yj5jPFwvc3ViPiwgczxzdWI+aTxcL3N1Yj4sIGRlc2NyaWJpbmcgdGhlIHNpemUgb2YgdGhlIG1lbW9yeSwgdGhlIHNpemUgb2YgdGhlIHByb2dyYW0gY29kZSBhbmQgdGhlIHNpemUgb2YgdGhlIGlucHV0ICgwICZsdDsgczxzdWI+bTxcL3N1Yj4gJmxlOyAxMDAgMDAwOyAwICZsdDsgczxzdWI+YzxcL3N1Yj4sIHM8c3ViPmk8XC9zdWI+ICZsdDsgNCAwOTYpLiBUaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgdGhlIGJyYWluZioqayBwcm9ncmFtIGNvZGUgdG8gYmUgZXhlY3V0ZWQ7IGl0IGNvbnNpc3RzIG9mIHM8c3ViPmM8XC9zdWI+IGNoYXJhY3RlcnMuIFRoZSB0aGlyZCBsaW5lIGNvbnRhaW5zIHRoZSBpbnB1dCBvZiB0aGUgcHJvZ3JhbSwgYXMgdGV4dCAob25seSBwcmludGFibGUsIG5vbi13aGl0ZXNwYWNlIGNoYXJhY3RlcnMpLjxcL3A+XHJcblxyXG48cD5PbmNlIHRoZSBwcm9ncmFtIGhhcyBjb25zdW1lZCBhbGwgYXZhaWxhYmxlIGlucHV0LCB0aGUgaW5wdXQgaW5zdHJ1Y3Rpb24gc2hhbGwgc2V0IHRoZSBjdXJyZW50IGNlbGwgdG8gMjU1LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgcHJpbnQgb25lIGxpbmUsIGNvbnRhaW5pbmcgZWl0aGVyICZxdW90O1Rlcm1pbmF0ZXMmcXVvdDsgb3IgJnF1b3Q7TG9vcHMmcXVvdDssIGRlcGVuZGluZyBvbiB3aGV0aGVyIHRoZSBwcm9ncmFtIGVpdGhlciB0ZXJtaW5hdGVzIGFmdGVyIGEgZmluaXRlIG51bWJlciBvZiBzdGVwcywgb3IgZW50ZXJzIGFuIGVuZGxlc3MgbG9vcC4gSWYgdGhlIHByb2dyYW0gbG9vcHMsIGFsc28gcHJpbnQgdGhlIGluZGljZXMgKDAtYmFzZWQpIG9mIHRoZSB0d28gWyBhbmQgdGhlIF0gc3ltYm9scyBpbiB0aGUgY29kZSBhcnJheSB0aGF0IGNvcnJlc3BvbmQgdG8gdGhlIGVuZGxlc3MgbG9vcC4gWW91IG1heSBzYWZlbHkgYXNzdW1lIHRoYXQgYWZ0ZXIgNTAgMDAwIDAwMCBpbnN0cnVjdGlvbnMsIGEgcHJvZ3JhbSBlaXRoZXIgdGVybWluYXRlZCBvciBoYW5ncyBpbiBhbiBlbmRsZXNzIGxvb3AsIHdoaWNoIHRoZW4gd2FzIGV4ZWN1dGVkIGF0IGxlYXN0IG9uY2UuIER1cmluZyBlYWNoIGl0ZXJhdGlvbiBvZiB0aGUgZW5kbGVzcyBsb29wIGF0IG1vc3QgNTAgMDAwIDAwMCBpbnN0cnVjdGlvbnMgYXJlIGV4ZWN1dGVkLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > German Collegiate Programming Contest > GCPC 2012 B번

  • 문제를 번역한 사람: baekjoon
  • 데이터를 추가한 사람: doju, jh05013
  • 빠진 조건을 찾은 사람: jh05013
  • 문제를 다시 작성한 사람: jh05013