시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 478 92 56 18.983%

문제

고창영은 스택을 조금 변형해서 고스택을 만들었다.

고스택은 숫자만을 저장할 수 있고, 다음과 같은 10가지 연산을 수행할 수 있다.

편의상 스택의 가장 위에 저장된 수를 첫번째 수라고 하고, 그 다음은 차례대로 두번째 수, 세번째 수라고 한다.

  • NUM X: X를 스택의 가장 위에 저장한다. (0 ≤ X ≤ 109)
  • POP: 스택 가장 위의 숫자를 제거한다.
  • INV: 첫번째 수의 부호를 바꾼다. (42 -> -42)
  • DUP: 첫번째 숫자를 하나 더 스택의 가장 위에 저장한다.
  • SWP: 첫번째 숫자와 두번째 숫자의 위치를 서로 바꾼다.
  • ADD: 첫번째 숫자와 두번째 숫자를 더한다.
  • SUB: 첫번째 숫자와 두번째 숫자를 뺀다. (두번째 - 첫번째)
  • MUL: 첫번째 숫자와 두번째 숫자를 곱한다.
  • DIV: 첫번째 숫자로 두번째 숫자를 나눈 몫을 저장한다. 두번째 숫자가 피제수, 첫번째 숫자가 제수이다.
  • MOD: 첫번째 숫자로 두번째 숫자를 나눈 나머지를 저장한다. 두번째 숫자가 피제수, 첫번째 숫자가 제수이다.

이항 연산자의 경우에 첫번째 숫자가 오른쪽에 있는 수이고, 두번째 숫자가 왼쪽에 있는 수이다. 또, 연산을 수행하기 전에 두 숫자를 모두 스택에서 제거한 뒤, 결과를 다시 스택에 저장하는 것이다.

숫자가 부족해서 연산을 수행할 수 없을 때, 0으로 나눴을 때 (DIV, MOD), 연산 결과의 절대값이 109를 넘어갈 때는 모두 프로그램 에러이다.

음수 나눗셈에 대한 모호함을 피하기 위해 다음과 같이 계산한다. 나눗셈의 피연산자에 음수가 있을 때는, 그 수를 절대값을 씌운 뒤 계산한다. 그리고 나서 몫과 나머지의 부호는 다음과 같이 결정한다. 피연산자중 음수가 한 개일때는 몫의 부호가 음수이다. 이 경우를 제외하면 몫의 부호는 항상 양수이다. 나머지의 부호는 피제수의 부호와 같다. 따라서, 13 div -4 = -3, -13 mod 4 = -1, -13 mod -4 = -1이다.

프로그램 에러가 발생했을 경우에는, 현재 프로그램의 수행을 멈추고, 그 다음 어떤 명령도 수행하지 않는다.

입력

입력은 기계 여러 대의 설명으로 이루어져 있다. 각 기계의 설명은 프로그램과 입력영역으로 나누어져 있다.

프로그램은 명령어로 이루어져 있고, 명령어는 한 줄에 하나씩 있다. 각 명령은 문제 설명에 나와있는 대문자 알파벳 3글자이고, 다른 글자는 주어지지 않는다. NUM의 경우에는 명령어 다음에 숫자가 주어지며, 이 숫자는 0보다 크거나 같고, 109보다 작거나 같은 정수이다. NUM과 숫자는 공백으로 구분되어져 있다. 각 프로그램은 END가 나오면 끝난다.

입력영역은 첫째 줄에 프로그램 수행 횟수 N이 있다. (0 ≤ N ≤ 10,000) 다음 N개의 줄에는 한 줄에 하나씩 입력값 Vi가 있다. (0 ≤ Vi ≤ 109) 각 입력값에 대해서 프로그램을 한 번씩 수행해야 하고, 이 수행은 모두 독립적이다. 매번 프로그램을 수행할 때, 스택에 들어있는 값은 입력값 Vi 하나이다.

각각의 기계 설명은 빈 줄로 구분되어져 있다. QUIT이 나오면 다음 기계 설명이 없다는 뜻이다. 명령어가 100,000개를 넘어가는 경우와 스택이 수행될 때, 1,000개 이상의 숫자를 저장하는 경우는 없다.

출력

각각의 입력값에 대해서, 해당하는 프로그램을 수행한 뒤, 출력값을 출력하면 된다. 출력값이란 스택에 저장되어 있는 숫자이다.

만약, 프로그램 에러가 발생하거나, 모든 수행이 종료됐을 때 스택에 저장되어 있는 숫자가 1개가 아니라면, "ERROR"를 출력한다.

각 기계에 대한 출력값을 모두 출력한 뒤에는 빈 줄을 하나 출력해야 한다.

예제 입력 1

DUP
MUL
NUM 2
ADD
END
3
1
10
50

NUM 1
NUM 1
ADD
END
2
42
43

NUM 600000000
ADD
END
3
0
600000000
1

QUIT

예제 출력 1

3
102
2502

ERROR
ERROR

600000000
ERROR
600000001
W3sicHJvYmxlbV9pZCI6IjM0MjUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjZTBcdWMyYTRcdWQwZGQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YWNlMFx1Y2MzZFx1YzYwMVx1Yzc0MCBcdWMyYTRcdWQwZGRcdWM3NDQgXHVjODcwXHVhZTA4IFx1YmNjMFx1ZDYxNVx1ZDU3NFx1YzExYyBcdWFjZTBcdWMyYTRcdWQwZGRcdWM3NDQgXHViOWNjXHViNGU0XHVjNWM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjZTBcdWMyYTRcdWQwZGRcdWM3NDAgXHVjMjJiXHVjNzkwXHViOWNjXHVjNzQ0IFx1YzgwMFx1YzdhNVx1ZDU2MCBcdWMyMTggXHVjNzg4XHVhY2UwLCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIDEwXHVhYzAwXHVjOWMwIFx1YzVmMFx1YzBiMFx1Yzc0NCBcdWMyMThcdWQ1ODlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkM2I4XHVjNzU4XHVjMGMxIFx1YzJhNFx1ZDBkZFx1Yzc1OCBcdWFjMDBcdWM3YTUgXHVjNzA0XHVjNWQwIFx1YzgwMFx1YzdhNVx1YjQxYyBcdWMyMThcdWI5N2MgXHVjY2FiXHViYzg4XHVjOWY4IFx1YzIxOFx1Yjc3Y1x1YWNlMCBcdWQ1NThcdWFjZTAsIFx1YWRmOCBcdWIyZTRcdWM3NGNcdWM3NDAgXHVjYzI4XHViODQwXHViMzAwXHViODVjIFx1YjQ1MFx1YmM4OFx1YzlmOCBcdWMyMTgsIFx1YzEzOFx1YmM4OFx1YzlmOCBcdWMyMThcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjxzdHJvbmc+TlVNIFg8XC9zdHJvbmc+OiBYXHViOTdjIFx1YzJhNFx1ZDBkZFx1Yzc1OCBcdWFjMDBcdWM3YTUgXHVjNzA0XHVjNWQwIFx1YzgwMFx1YzdhNVx1ZDU1Y1x1YjJlNC4gKDAgJmxlOyBYICZsZTsgMTA8c3VwPjk8XC9zdXA+KTxcL2xpPlxyXG5cdDxsaT48c3Ryb25nPlBPUDxcL3N0cm9uZz46IFx1YzJhNFx1ZDBkZCBcdWFjMDBcdWM3YTUgXHVjNzA0XHVjNzU4IFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWM4MWNcdWFjNzBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPjxzdHJvbmc+SU5WPFwvc3Ryb25nPjogXHVjY2FiXHViYzg4XHVjOWY4IFx1YzIxOFx1Yzc1OCBcdWJkODBcdWQ2MzhcdWI5N2MgXHViYzE0XHVhZmJjXHViMmU0LiAoNDIgLSZndDsgLTQyKTxcL2xpPlxyXG5cdDxsaT48c3Ryb25nPkRVUDxcL3N0cm9uZz46IFx1Y2NhYlx1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTBcdWI5N2MgXHVkNTU4XHViMDk4IFx1YjM1NCBcdWMyYTRcdWQwZGRcdWM3NTggXHVhYzAwXHVjN2E1IFx1YzcwNFx1YzVkMCBcdWM4MDBcdWM3YTVcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPjxzdHJvbmc+U1dQPFwvc3Ryb25nPjogXHVjY2FiXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1YzY0MCBcdWI0NTBcdWJjODhcdWM5ZjggXHVjMjJiXHVjNzkwXHVjNzU4IFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWMxMWNcdWI4NWMgXHViYzE0XHVhZmJjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT48c3Ryb25nPkFERDxcL3N0cm9uZz46IFx1Y2NhYlx1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTBcdWM2NDAgXHViNDUwXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWIzNTRcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPjxzdHJvbmc+U1VCPFwvc3Ryb25nPjogXHVjY2FiXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1YzY0MCBcdWI0NTBcdWJjODhcdWM5ZjggXHVjMjJiXHVjNzkwXHViOTdjIFx1YmU4MFx1YjJlNC4gKFx1YjQ1MFx1YmM4OFx1YzlmOCAtIFx1Y2NhYlx1YmM4OFx1YzlmOCk8XC9saT5cclxuXHQ8bGk+PHN0cm9uZz5NVUw8XC9zdHJvbmc+OiBcdWNjYWJcdWJjODhcdWM5ZjggXHVjMjJiXHVjNzkwXHVjNjQwIFx1YjQ1MFx1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTBcdWI5N2MgXHVhY2YxXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT48c3Ryb25nPkRJVjxcL3N0cm9uZz46IFx1Y2NhYlx1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTBcdWI4NWMgXHViNDUwXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWIwOThcdWIyMDggXHViYWFiXHVjNzQ0IFx1YzgwMFx1YzdhNVx1ZDU1Y1x1YjJlNC4gXHViNDUwXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWQ1M2NcdWM4MWNcdWMyMTgsIFx1Y2NhYlx1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTBcdWFjMDAgXHVjODFjXHVjMjE4XHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT48c3Ryb25nPk1PRDxcL3N0cm9uZz46IFx1Y2NhYlx1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTBcdWI4NWMgXHViNDUwXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1YzgwMFx1YzdhNVx1ZDU1Y1x1YjJlNC4gXHViNDUwXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWQ1M2NcdWM4MWNcdWMyMTgsIFx1Y2NhYlx1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTBcdWFjMDAgXHVjODFjXHVjMjE4XHVjNzc0XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvc3RtYy5wbmdcIiBzdHlsZT1cImhlaWdodDoxMDBweDsgd2lkdGg6NTE0cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHVkNTZkIFx1YzVmMFx1YzBiMFx1Yzc5MFx1Yzc1OCBcdWFjYmRcdWM2YjBcdWM1ZDAgXHVjY2FiXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzIxOFx1Yzc3NFx1YWNlMCwgXHViNDUwXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWM2N2NcdWNhYmRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzIxOFx1Yzc3NFx1YjJlNC4gXHViNjEwLCBcdWM1ZjBcdWMwYjBcdWM3NDQgXHVjMjE4XHVkNTg5XHVkNTU4XHVhZTMwIFx1YzgwNFx1YzVkMCBcdWI0NTAgXHVjMjJiXHVjNzkwXHViOTdjIFx1YmFhOFx1YjQ1MCBcdWMyYTRcdWQwZGRcdWM1ZDBcdWMxMWMgXHVjODFjXHVhYzcwXHVkNTVjIFx1YjRhNCwgXHVhY2IwXHVhY2ZjXHViOTdjIFx1YjJlNFx1YzJkYyBcdWMyYTRcdWQwZGRcdWM1ZDAgXHVjODAwXHVjN2E1XHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMjJiXHVjNzkwXHVhYzAwIFx1YmQ4MFx1Yzg3MVx1ZDU3NFx1YzExYyBcdWM1ZjBcdWMwYjBcdWM3NDQgXHVjMjE4XHVkNTg5XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWM3NDQgXHViNTRjLCAwXHVjNzNjXHViODVjIFx1YjA5OFx1YjIzNFx1Yzc0NCBcdWI1NGMgKERJViwgTU9EKSwgXHVjNWYwXHVjMGIwIFx1YWNiMFx1YWNmY1x1Yzc1OCBcdWM4MDhcdWIzMDBcdWFjMTJcdWM3NzQgMTA8c3VwPjk8XC9zdXA+XHViOTdjIFx1YjExOFx1YzViNFx1YWMwOCBcdWI1NGNcdWIyOTQgXHViYWE4XHViNDUwIFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOCBcdWM1ZDBcdWI3ZWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc0Y1x1YzIxOCBcdWIwOThcdWIyMTdcdWMxNDhcdWM1ZDAgXHViMzAwXHVkNTVjIFx1YmFhOFx1ZDYzOFx1ZDU2OFx1Yzc0NCBcdWQ1M2NcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVhY2M0XHVjMGIwXHVkNTVjXHViMmU0LiBcdWIwOThcdWIyMTdcdWMxNDhcdWM3NTggXHVkNTNjXHVjNWYwXHVjMGIwXHVjNzkwXHVjNWQwIFx1Yzc0Y1x1YzIxOFx1YWMwMCBcdWM3ODhcdWM3NDQgXHViNTRjXHViMjk0LCBcdWFkZjggXHVjMjE4XHViOTdjIFx1YzgwOFx1YjMwMFx1YWMxMlx1Yzc0NCBcdWM1MGNcdWM2YjQgXHViNGE0IFx1YWNjNFx1YzBiMFx1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIFx1YjA5OFx1YzExYyBcdWJhYWJcdWFjZmMgXHViMDk4XHViYTM4XHVjOWMwXHVjNzU4IFx1YmQ4MFx1ZDYzOFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YWNiMFx1YzgxNVx1ZDU1Y1x1YjJlNC4gXHVkNTNjXHVjNWYwXHVjMGIwXHVjNzkwXHVjOTExIFx1Yzc0Y1x1YzIxOFx1YWMwMCBcdWQ1NWMgXHVhYzFjXHVjNzdjXHViNTRjXHViMjk0IFx1YmFhYlx1Yzc1OCBcdWJkODBcdWQ2MzhcdWFjMDAgXHVjNzRjXHVjMjE4XHVjNzc0XHViMmU0LiBcdWM3NzQgXHVhY2JkXHVjNmIwXHViOTdjIFx1YzgxY1x1YzY3OFx1ZDU1OFx1YmE3NCBcdWJhYWJcdWM3NTggXHViZDgwXHVkNjM4XHViMjk0IFx1ZDU2ZFx1YzBjMSBcdWM1OTFcdWMyMThcdWM3NzRcdWIyZTQuIFx1YjA5OFx1YmEzOFx1YzljMFx1Yzc1OCBcdWJkODBcdWQ2MzhcdWIyOTQgXHVkNTNjXHVjODFjXHVjMjE4XHVjNzU4IFx1YmQ4MFx1ZDYzOFx1YzY0MCBcdWFjMTlcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgMTMgZGl2IC00ID0gLTMsIC0xMyBtb2QgNCA9IC0xLCAtMTMgbW9kIC00ID0gLTFcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOCBcdWM1ZDBcdWI3ZWNcdWFjMDAgXHViYzFjXHVjMGRkXHVkNTg4XHVjNzQ0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCwgXHVkNjA0XHVjN2FjIFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc1OCBcdWMyMThcdWQ1ODlcdWM3NDQgXHViYTQ4XHVjZDk0XHVhY2UwLCBcdWFkZjggXHViMmU0XHVjNzRjIFx1YzViNFx1YjVhNCBcdWJhODVcdWI4MzlcdWIzYzQgXHVjMjE4XHVkNTg5XHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWFlMzBcdWFjYzQgXHVjNWVjXHViN2VjIFx1YjMwMFx1Yzc1OCBcdWMxMjRcdWJhODVcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1YWUzMFx1YWNjNFx1Yzc1OCBcdWMxMjRcdWJhODVcdWM3NDAgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVhY2ZjIFx1Yzc4NVx1YjgyNVx1YzYwMVx1YzVlZFx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDRcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDAgXHViYTg1XHViODM5XHVjNWI0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1YmE4NVx1YjgzOVx1YzViNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWJhODVcdWI4MzlcdWM3NDAgXHViYjM4XHVjODFjIFx1YzEyNFx1YmE4NVx1YzVkMCBcdWIwOThcdWM2NDBcdWM3ODhcdWIyOTQgXHViMzAwXHViYjM4XHVjNzkwIFx1YzU0Y1x1ZDMwY1x1YmNiMyAzXHVhZTAwXHVjNzkwXHVjNzc0XHVhY2UwLCBcdWIyZTRcdWI5NzggXHVhZTAwXHVjNzkwXHViMjk0IFx1YzhmY1x1YzViNFx1YzljMFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIE5VTVx1Yzc1OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHViYTg1XHViODM5XHVjNWI0IFx1YjJlNFx1Yzc0Y1x1YzVkMCBcdWMyMmJcdWM3OTBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBcdWM3NzQgXHVjMjJiXHVjNzkwXHViMjk0IDBcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgMTA8c3VwPjk8XC9zdXA+XHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LiBOVU1cdWFjZmMgXHVjMjJiXHVjNzkwXHViMjk0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQwIEVORFx1YWMwMCBcdWIwOThcdWM2MjRcdWJhNzQgXHViMDVkXHViMDljXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3ODVcdWI4MjVcdWM2MDFcdWM1ZWRcdWM3NDAgXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YTggXHVjMjE4XHVkNTg5IFx1ZDY5Zlx1YzIxOCBOXHVjNzc0IFx1Yzc4OFx1YjJlNC4gKDAgJmxlOyBOICZsZTsgMTAsMDAwKSBcdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjNzg1XHViODI1XHVhYzEyIFY8c3ViPmk8XC9zdWI+XHVhYzAwIFx1Yzc4OFx1YjJlNC4gKDAgJmxlOyBWPHN1Yj5pPFwvc3ViPiAmbGU7IDEwPHN1cD45PFwvc3VwPikgXHVhYzAxIFx1Yzc4NVx1YjgyNVx1YWMxMlx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1ZDU1YyBcdWJjODhcdWM1MjkgXHVjMjE4XHVkNTg5XHVkNTc0XHVjNTdjIFx1ZDU1OFx1YWNlMCwgXHVjNzc0IFx1YzIxOFx1ZDU4OVx1Yzc0MCBcdWJhYThcdWI0NTAgXHViM2M1XHViOWJkXHVjODAxXHVjNzc0XHViMmU0LiBcdWI5ZTRcdWJjODggXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1YzIxOFx1ZDU4OVx1ZDU2MCBcdWI1NGMsIFx1YzJhNFx1ZDBkZFx1YzVkMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyOTQgXHVhYzEyXHVjNzQwIFx1Yzc4NVx1YjgyNVx1YWMxMiBWPHN1Yj5pPFwvc3ViPiBcdWQ1NThcdWIwOThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWFlMzBcdWFjYzQgXHVjMTI0XHViYTg1XHVjNzQwIFx1YmU0OCBcdWM5MDRcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gUVVJVFx1Yzc3NCBcdWIwOThcdWM2MjRcdWJhNzQgXHViMmU0XHVjNzRjIFx1YWUzMFx1YWNjNCBcdWMxMjRcdWJhODVcdWM3NzQgXHVjNWM2XHViMmU0XHViMjk0IFx1YjczYlx1Yzc3NFx1YjJlNC4gXHViYTg1XHViODM5XHVjNWI0XHVhYzAwIDEwMCwwMDBcdWFjMWNcdWI5N2MgXHViMTE4XHVjNWI0XHVhYzAwXHViMjk0IFx1YWNiZFx1YzZiMFx1YzY0MCBcdWMyYTRcdWQwZGRcdWM3NzQgXHVjMjE4XHVkNTg5XHViNDIwIFx1YjU0YywgMSwwMDBcdWFjMWMgXHVjNzc0XHVjMGMxXHVjNzU4IFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWM4MDBcdWM3YTVcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVjNzg1XHViODI1XHVhYzEyXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVkNTc0XHViMmY5XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWMyMThcdWQ1ODlcdWQ1NWMgXHViNGE0LCBcdWNkOWNcdWI4MjVcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC4gXHVjZDljXHViODI1XHVhYzEyXHVjNzc0XHViNzgwIFx1YzJhNFx1ZDBkZFx1YzVkMCBcdWM4MDBcdWM3YTVcdWI0MThcdWM1YjQgXHVjNzg4XHViMjk0IFx1YzIyYlx1Yzc5MFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWNjXHVjNTdkLCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YTggXHVjNWQwXHViN2VjXHVhYzAwIFx1YmMxY1x1YzBkZFx1ZDU1OFx1YWM3MFx1YjA5OCwgXHViYWE4XHViNGUwIFx1YzIxOFx1ZDU4OVx1Yzc3NCBcdWM4ODVcdWI4Y2NcdWI0MTBcdWM3NDQgXHViNTRjIFx1YzJhNFx1ZDBkZFx1YzVkMCBcdWM4MDBcdWM3YTVcdWI0MThcdWM1YjQgXHVjNzg4XHViMjk0IFx1YzIyYlx1Yzc5MFx1YWMwMCAxXHVhYzFjXHVhYzAwIFx1YzU0NFx1YjJjOFx1Yjc3Y1x1YmE3NCwgJnF1b3Q7RVJST1ImcXVvdDtcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVhZTMwXHVhY2M0XHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWNkOWNcdWI4MjVcdWFjMTJcdWM3NDQgXHViYWE4XHViNDUwIFx1Y2Q5Y1x1YjgyNVx1ZDU1YyBcdWI0YTRcdWM1ZDBcdWIyOTQgXHViZTQ4IFx1YzkwNFx1Yzc0NCBcdWQ1NThcdWIwOTggXHVjZDljXHViODI1XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzNDI1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU3RhY2sgTWFjaGluZSBFeGVjdXRvciIsImRlc2NyaXB0aW9uIjoiPHA+TWFueSBjaXBoZXJzIGNhbiBiZSBjb21wdXRlZCBtdWNoIGZhc3RlciB1c2luZyB2YXJpb3VzIG1hY2hpbmVzIGFuZCBhdXRvbWF0YS4gSW4gdGhpcyBwcm9ibGVtLCB3ZSB3aWxsIGZvY3VzIG9uIG9uZSBwYXJ0aWN1bGFyIHR5cGUgb2YgbWFjaGluZXMgY2FsbGVkIHN0YWNrIG1hY2hpbmUuIEl0cyBuYW1lIGNvbWVzIGZyb20gdGhlIGZhY3QgdGhhdCB0aGUgbWFjaGluZSBvcGVyYXRlcyB3aXRoIHRoZSB3ZWxsLWtub3duIGRhdGEgc3RydWN0dXJlICZtZGFzaDsgc3RhY2suIFRoZSBsYXRlci1zdG9yZWQgdmFsdWVzIGFyZSBvbiB0aGUgdG9wLCBvbGRlciB2YWx1ZXMgYXQgdGhlIGJvdHRvbS4gTWFjaGluZSBpbnN0cnVjdGlvbnMgdHlwaWNhbGx5IG1hbmlwdWxhdGUgdGhlIHRvcCBvZiB0aGUgc3RhY2sgb25seS48XC9wPlxyXG5cclxuPHA+T3VyIHN0YWNrIG1hY2hpbmUgaXMgcmVsYXRpdmVseSBzaW1wbGU6IEl0IHdvcmtzIHdpdGggaW50ZWdlciBudW1iZXJzIG9ubHksIGl0IGhhcyBubyBzdG9yYWdlIGJlc2lkZSB0aGUgc3RhY2sgKG5vIHJlZ2lzdGVycyBldGMuKSBhbmQgbm8gc3BlY2lhbCBpbnB1dCBvciBvdXRwdXQgZGV2aWNlcy4gVGhlIHNldCBvZiBpbnN0cnVjdGlvbnMgaXMgYXMgZm9sbG93czo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT48c3Ryb25nPk5VTSBYPFwvc3Ryb25nPiwgd2hlcmUgWCBpcyBhIG5vbi1uZWdhdGl2ZSBpbnRlZ2VyIG51bWJlciwgMCAmbGU7IFggJmxlOyAxMDxzdXA+OTxcL3N1cD4uIFRoZSBOVU0gaW5zdHJ1Y3Rpb24gc3RvcmVzIHRoZSBudW1iZXIgWCBvbiB0b3Agb2YgdGhlIHN0YWNrLiBJdCBpcyB0aGUgb25seSBwYXJhbWV0cml6ZWQgaW5zdHJ1Y3Rpb24uPFwvbGk+XHJcblx0PGxpPjxzdHJvbmc+UE9QPFwvc3Ryb25nPjogcmVtb3ZlcyB0aGUgdG9wIG51bWJlciBmcm9tIHRoZSBzdGFjay48XC9saT5cclxuXHQ8bGk+PHN0cm9uZz5JTlY8XC9zdHJvbmc+OiBjaGFuZ2VzIHRoZSBzaWduIG9mIHRoZSB0b3AtbW9zdCBudW1iZXIuICg0MiAmcmFycjsgJm1pbnVzOzQyKTxcL2xpPlxyXG5cdDxsaT48c3Ryb25nPkRVUDxcL3N0cm9uZz46IGR1cGxpY2F0ZXMgdGhlIHRvcC1tb3N0IG51bWJlciBvbiB0aGUgc3RhY2suPFwvbGk+XHJcblx0PGxpPjxzdHJvbmc+U1dQPFwvc3Ryb25nPjogc3dhcHMgKGV4Y2hhbmdlcykgdGhlIHBvc2l0aW9uIG9mIHR3byB0b3AtbW9zdCBudW1iZXJzLjxcL2xpPlxyXG5cdDxsaT48c3Ryb25nPkFERDxcL3N0cm9uZz46IGFkZHMgdHdvIG51bWJlcnMgb24gdGhlIHRvcCBvZiB0aGUgc3RhY2suPFwvbGk+XHJcblx0PGxpPjxzdHJvbmc+U1VCPFwvc3Ryb25nPjogc3VidHJhY3RzIHRoZSB0b3AtbW9zdCBudW1iZXIgZnJvbSB0aGUgJmxkcXVvO3NlY29uZCBvbmUmcmRxdW87ICh0aGUgb25lIGJlbG93KS48XC9saT5cclxuXHQ8bGk+PHN0cm9uZz5NVUw8XC9zdHJvbmc+OiBtdWx0aXBsaWVzIHR3byBudW1iZXJzIG9uIHRoZSB0b3Agb2YgdGhlIHN0YWNrLjxcL2xpPlxyXG5cdDxsaT48c3Ryb25nPkRJVjxcL3N0cm9uZz46IGludGVnZXIgZGl2aXNvbiBvZiB0d28gbnVtYmVycyBvbiB0aGUgdG9wLiBUaGUgdG9wLW1vc3QgbnVtYmVyIGJlY29tZXMgZGl2aXNvciwgdGhlIG9uZSBiZWxvdyBkaXZpZGVuZC4gVGhlIHF1b3RpZW50IHdpbGwgYmUgc3RvcmVkIGFzIHRoZSByZXN1bHQuPFwvbGk+XHJcblx0PGxpPjxzdHJvbmc+TU9EPFwvc3Ryb25nPjogbW9kdWxvIG9wZXJhdGlvbi4gVGhlIG9wZXJhbmRzIGFyZSB0aGUgc2FtZSBhcyBmb3IgdGhlIGRpdmlzaW9uIGJ1dCB0aGUgcmVtYWluZGVyIGlzIHN0b3JlZCBhcyB0aGUgcmVzdWx0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvc3RtYy5wbmdcIiBzdHlsZT1cImhlaWdodDoxMDBweDsgb3BhY2l0eTowLjk7IHdpZHRoOjUxNHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkFsbCBiaW5hcnkgb3BlcmF0aW9ucyBjb25zaWRlciB0aGUgdG9wLW1vc3QgbnVtYmVyIHRvIGJlIHRoZSAmbGRxdW87cmlnaHQmcmRxdW87IG9wZXJhbmQsIHRoZSBzZWNvbmQgbnVtYmVyIHRoZSAmbGRxdW87bGVmdCZyZHF1bzsgb25lLiBBbGwgb2YgdGhlbSByZW1vdmUgYm90aCBvcGVyYW5kcyBmcm9tIHRoZSBzdGFjayBhbmQgcGxhY2UgdGhlIHJlc3VsdCBvbiB0b3AgaW4gcGxhY2Ugb2YgdGhlIG9yaWdpbmFsIG51bWJlcnMuPFwvcD5cclxuXHJcbjxwPklmIHRoZXJlIGFyZSBub3QgZW5vdWdoIG51bWJlcnMgb24gdGhlIHN0YWNrIGZvciBhbiBpbnN0cnVjdGlvbiAob25lIG9yIHR3byksIHRoZSBleGVjdXRpb24gb2Ygc3VjaCBhbiBpbnN0cnVjdGlvbiB3aWxsIHJlc3VsdCBpbnRvIGEgcHJvZ3JhbSBmYWlsdXJlLiBBIGZhaWx1cmUgYWxzbyBvY2N1cnMgaWYgYSBkaXZpc29yIGJlY29tZXMgemVybyAoZm9yIERJViBvciBNT0QpIG9yIGlmIHRoZSByZXN1bHQgb2YgYW55IG9wZXJhdGlvbiBzaG91bGQgYmUgbW9yZSB0aGFuIDEwPHN1cD45PFwvc3VwPiBpbiBhYnNvbHV0ZSB2YWx1ZS4gVGhpcyBtZWFucyB0aGF0IHRoZSBtYWNoaW5lIG9ubHkgb3BlcmF0ZXMgd2l0aCBudW1iZXJzIGJldHdlZW4gJm1pbnVzOzEgMDAwIDAwMCAwMDAgYW5kIDEgMDAwIDAwMCAwMDAsIGluY2x1c2l2ZS48XC9wPlxyXG5cclxuPHA+VG8gYXZvaWQgYW1iaWd1aXRpZXMgd2hpbGUgd29ya2luZyB3aXRoIG5lZ2F0aXZlIGRpdmlzb3JzIGFuZCByZW1haW5kZXJzOiBJZiBzb21lIG9wZXJhbmQgb2YgYSBkaXZpc2lvbiBvcGVyYXRpb24gaXMgbmVnYXRpdmUsIHRoZSBhYnNvbHV0ZSB2YWx1ZSBvZiB0aGUgcmVzdWx0IHNob3VsZCBhbHdheXMgYmUgY29tcHV0ZWQgd2l0aCBhYnNvbHV0ZSB2YWx1ZXMgb2Ygb3BlcmFuZHMsIGFuZCB0aGUgc2lnbiBpcyBkZXRlcm1pbmVkIGFzIGZvbGxvd3M6IFRoZSBxdW90aWVudCBpcyBuZWdhdGl2ZSBpZiAoYW5kIG9ubHkgaWYpIGV4YWN0bHkgb25lIG9mIHRoZSBvcGVyYW5kcyBpcyBuZWdhdGl2ZS4gVGhlIHJlbWFpbmRlciBoYXMgdGhlIHNhbWUgc2lnbiBhcyB0aGUgZGl2aWRlbmQuIFRodXMsIDEzIGRpdiAmbWludXM7NCA9ICZtaW51czszLCAmbWludXM7MTMgbW9kIDQgPSAmbWludXM7MSwgJm1pbnVzOzEzIG1vZCAmbWludXM7NCA9ICZtaW51czsxLCBldGM8XC9wPlxyXG5cclxuPHA+SWYgYSBmYWlsdXJlIG9jY3VycyBmb3IgYW55IHJlYXNvbiwgdGhlIG1hY2hpbmUgc3RvcHMgdGhlIGV4ZWN1dGlvbiBvZiB0aGUgY3VycmVudCBwcm9ncmFtIGFuZCBubyBvdGhlciBpbnN0cnVjdGlvbnMgYXJlIGV2YWx1YXRlZCBpbiB0aGF0IHByb2dyYW0gcnVuLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnRhaW5zIGRlc2NyaXB0aW9uIG9mIHNldmVyYWwgbWFjaGluZXMuIEVhY2ggbWFjaGluZSBpcyBkZXNjcmliZWQgYnkgdHdvIHBhcnRzOiB0aGUgcHJvZ3JhbSBhbmQgdGhlIGlucHV0IHNlY3Rpb24uPFwvcD5cclxuXHJcbjxwPlRoZSBwcm9ncmFtIGlzIGdpdmVuIGJ5IGEgc2VyaWVzIG9mIGluc3RydWN0aW9ucywgb25lIHBlciBsaW5lLiBFdmVyeSBpbnN0cnVjdGlvbiBpcyBnaXZlbiBieSB0aHJlZSB1cHBlcmNhc2UgbGV0dGVycyBhbmQgdGhlcmUgbXVzdCBub3QgYmUgYW55IG90aGVyIGNoYXJhY3RlcnMuIFRoZSBvbmx5IGV4Y2VwdGlvbiBpcyB0aGUgTlVNIGluc3RydWN0aW9uLCB3aGljaCBoYXMgZXhhY3RseSBvbmUgc3BhY2UgYWZ0ZXIgdGhlIHRocmVlIGxldHRlcnMgZm9sbG93ZWQgYnkgYSBub24tbmVnYXRpdmUgaW50ZWdlciBudW1iZXIgYmV0d2VlbiAwIGFuZCAxMDxzdXA+OTxcL3N1cD4uIFRoZSBvbmx5IGFsbG93ZWQgaW5zdHJ1Y3Rpb25zIGFyZSB0aG9zZSBkZVx1ZmIwMW5lZCBhYm92ZS4gRWFjaCBwcm9ncmFtIGlzIHRlcm1pbmF0ZWQgYnkgYSBsaW5lIGNvbnRhaW5pbmcgdGhlIHdvcmQgJmxkcXVvO0VORCZyZHF1bzsgKGFuZCBub3RoaW5nIGVsc2UpLjxcL3A+XHJcblxyXG48cD5UaGUgaW5wdXQgc2VjdGlvbiBzdGFydHMgd2l0aCBhbiBpbnRlZ2VyIE4gKDAgJmxlOyBOICZsZTsgMTAgMDAwKSwgdGhlIG51bWJlciBvZiBwcm9ncmFtIGV4ZWN1dGlvbnMuIFRoZSBuZXh0IE4gbGluZXMgY29udGFpbiBvbmUgbnVtYmVyIGVhY2gsIHNwZWNpZnlpbmcgYW4gaW5wdXQgdmFsdWUgVjxzdWI+aTxcL3N1Yj4sIDAgJmxlOyBWPHN1Yj5pPFwvc3ViPiAmbGU7IDEwPHN1cD45PFwvc3VwPi4gVGhlIHByb2dyYW0gc2hvdWxkIGJlIGV4ZWN1dGVkIG9uY2UgZm9yIGVhY2ggb2YgdGhlc2UgdmFsdWVzIGluZGVwZW5kZW50bHksIGV2ZXJ5IGV4ZWN1dGlvbiBzdGFydGluZyB3aXRoIHRoZSBzdGFjayBjb250YWluaW5nIG9uZSBudW1iZXIgJm1kYXNoOyB0aGUgaW5wdXQgdmFsdWUgVjxzdWI+aTxcL3N1Yj4uPFwvcD5cclxuXHJcbjxwPlRoZXJlIGlzIG9uZSBlbXB0eSBsaW5lIGF0IHRoZSBhbmQgb2YgZWFjaCBtYWNoaW5lIGRlc2NyaXB0aW9uLiBUaGUgbGFzdCBtYWNoaW5lIGlzIGZvbGxvd2VkIGJ5IGEgbGluZSBjb250YWluaW5nIHRoZSB3b3JkICZsZHF1bztRVUlUJnJkcXVvOy4gTm8gcHJvZ3JhbSB3aWxsIGNvbnRhaW4gbW9yZSB0aGFuIDEwMCAwMDAgaW5zdHJ1Y3Rpb25zIGFuZCBubyBwcm9ncmFtIHJlcXVpcmVzIG1vcmUgdGhhbiAxIDAwMCBudW1iZXJzIG9uIHRoZSBzdGFjayBpbiBhbnkgbW9tZW50IGR1cmluZyBpdHMgZXhlY3V0aW9uLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGlucHV0IHZhbHVlLCBwcmludCBvbmUgbGluZSBjb250YWluaW5nIHRoZSBvdXRwdXQgdmFsdWUgZm9yIHRoZSBjb3JyZXNwb25kaW5nIGV4ZWN1dGlvbiwgaS5lLiwgdGhlIG9uZSBudW1iZXIgdGhhdCB3aWxsIGJlIG9uIHRoZSBzdGFjayBhZnRlciB0aGUgcHJvZ3JhbSBleGVjdXRlcyB3aXRoIHRoZSBpbml0aWFsIHN0YWNrIGNvbnRhaW5pbmcgb25seSB0aGUgaW5wdXQgbnVtYmVyLjxcL3A+XHJcblxyXG48cD5JZiB0aGVyZSBpcyBhIHByb2dyYW0gZmFpbHVyZSBkdXJpbmcgdGhlIGV4ZWN1dGlvbiBvciBpZiB0aGUgc3RhY2sgc2l6ZSBpcyBpbmNvcnJlY3QgYXQgdGhlIGVuZCBvZiB0aGUgcnVuIChlaXRoZXIgZW1wdHkgb3IgdGhlcmUgYXJlIG1vcmUgbnVtYmVycyB0aGFuIG9uZSksIHByaW50IHRoZSB3b3JkICZsZHF1bztFUlJPUiZyZHF1bzsgaW5zdGVhZC48XC9wPlxyXG5cclxuPHA+UHJpbnQgb25lIGVtcHR5IGxpbmUgYWZ0ZXIgZWFjaCBtYWNoaW5lLCBpbmNsdWRpbmcgdGhlIGxhc3Qgb25lLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

ACM-ICPC > Regionals > Europe > Central European Regional Contest > CERC 2011 J번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: jh05013
  • 데이터를 추가한 사람: kdk8361