시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 530 96 60 17.647%

문제

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

고스택은 숫자만을 저장할 수 있고, 다음과 같은 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+XHVkM2I4XHVjNzU4XHVjMGMxIFx1YzJhNFx1ZDBkZFx1Yzc1OCBcdWFjMDBcdWM3YTUgXHVjNzA0XHVjNWQwIFx1YzgwMFx1YzdhNVx1YjQxYyBcdWMyMThcdWI5N2MgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWMyMThcdWI3N2NcdWFjZTAgXHVkNTU4XHVhY2UwLCBcdWFkZjggXHViMmU0XHVjNzRjXHVjNzQwIFx1Y2MyOFx1Yjg0MFx1YjMwMFx1Yjg1YyBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzIxOCwgXHVjMTM4IFx1YmM4OFx1YzlmOCBcdWMyMThcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjxzdHJvbmc+TlVNIFg8XC9zdHJvbmc+OiBYXHViOTdjIFx1YzJhNFx1ZDBkZFx1Yzc1OCBcdWFjMDBcdWM3YTUgXHVjNzA0XHVjNWQwIFx1YzgwMFx1YzdhNVx1ZDU1Y1x1YjJlNC4gKDAgJmxlOyBYICZsZTsgMTA8c3VwPjk8XC9zdXA+KTxcL2xpPlxyXG5cdDxsaT48c3Ryb25nPlBPUDxcL3N0cm9uZz46IFx1YzJhNFx1ZDBkZCBcdWFjMDBcdWM3YTUgXHVjNzA0XHVjNzU4IFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWM4MWNcdWFjNzBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPjxzdHJvbmc+SU5WPFwvc3Ryb25nPjogXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWMyMThcdWM3NTggXHViZDgwXHVkNjM4XHViOTdjIFx1YmMxNFx1YWZiY1x1YjJlNC4gKDQyIC0mZ3Q7IC00Mik8XC9saT5cclxuXHQ8bGk+PHN0cm9uZz5EVVA8XC9zdHJvbmc+OiBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWQ1NThcdWIwOTggXHViMzU0IFx1YzJhNFx1ZDBkZFx1Yzc1OCBcdWFjMDBcdWM3YTUgXHVjNzA0XHVjNWQwIFx1YzgwMFx1YzdhNVx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+PHN0cm9uZz5TV1A8XC9zdHJvbmc+OiBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1YzY0MCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1Yzc1OCBcdWM3MDRcdWNlNThcdWI5N2MgXHVjMTFjXHViODVjIFx1YmMxNFx1YWZiY1x1YjJlNC48XC9saT5cclxuXHQ8bGk+PHN0cm9uZz5BREQ8XC9zdHJvbmc+OiBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1YzY0MCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWIzNTRcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPjxzdHJvbmc+U1VCPFwvc3Ryb25nPjogXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTBcdWM2NDAgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTBcdWI5N2MgXHViZTgwXHViMmU0LiAoXHViNDUwIFx1YmM4OFx1YzlmOCAtIFx1Y2NhYiBcdWJjODhcdWM5ZjgpPFwvbGk+XHJcblx0PGxpPjxzdHJvbmc+TVVMPFwvc3Ryb25nPjogXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTBcdWM2NDAgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTBcdWI5N2MgXHVhY2YxXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT48c3Ryb25nPkRJVjxcL3N0cm9uZz46IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjMjJiXHVjNzkwXHViODVjIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjMjJiXHVjNzkwXHViOTdjIFx1YjA5OFx1YjIwOCBcdWJhYWJcdWM3NDQgXHVjODAwXHVjN2E1XHVkNTVjXHViMmU0LiBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWQ1M2NcdWM4MWNcdWMyMTgsIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjMjJiXHVjNzkwXHVhYzAwIFx1YzgxY1x1YzIxOFx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+PHN0cm9uZz5NT0Q8XC9zdHJvbmc+OiBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1Yjg1YyBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1YzgwMFx1YzdhNVx1ZDU1Y1x1YjJlNC4gXHViNDUwIFx1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTBcdWFjMDAgXHVkNTNjXHVjODFjXHVjMjE4LCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWM4MWNcdWMyMThcdWM3NzRcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9zdG1jLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEwMHB4OyB3aWR0aDo1MTRweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWQ1NmQgXHVjNWYwXHVjMGIwXHVjNzkwXHVjNzU4IFx1YWNiZFx1YzZiMFx1YzVkMCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzIxOFx1Yzc3NFx1YWNlMCwgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTBcdWFjMDAgXHVjNjdjXHVjYWJkXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMyMThcdWM3NzRcdWIyZTQuIFx1YjYxMCwgXHVjNWYwXHVjMGIwXHVjNzQ0IFx1YzIxOFx1ZDU4OVx1ZDU1OFx1YWUzMCBcdWM4MDRcdWM1ZDAgXHViNDUwIFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWJhYThcdWI0NTAgXHVjMmE0XHVkMGRkXHVjNWQwXHVjMTFjIFx1YzgxY1x1YWM3MFx1ZDU1YyBcdWI0YTQsIFx1YWNiMFx1YWNmY1x1Yjk3YyBcdWIyZTRcdWMyZGMgXHVjMmE0XHVkMGRkXHVjNWQwIFx1YzgwMFx1YzdhNVx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzIyYlx1Yzc5MFx1YWMwMCBcdWJkODBcdWM4NzFcdWQ1NzRcdWMxMWMgXHVjNWYwXHVjMGIwXHVjNzQ0IFx1YzIxOFx1ZDU4OVx1ZDU2MCBcdWMyMTggXHVjNWM2XHVjNzQ0IFx1YjU0YywgMFx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMzRcdWM3NDQgXHViNTRjIChESVYsIE1PRCksIFx1YzVmMFx1YzBiMCBcdWFjYjBcdWFjZmNcdWM3NTggXHVjODA4XHViMzAwXHVhYzEyXHVjNzc0IDEwPHN1cD45PFwvc3VwPlx1Yjk3YyBcdWIxMThcdWM1YjRcdWFjMDggXHViNTRjXHViMjk0IFx1YmFhOFx1YjQ1MCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YTggXHVjNWQwXHViN2VjXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NGNcdWMyMTggXHViMDk4XHViMjE3XHVjMTQ4XHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWJhYThcdWQ2MzhcdWQ1NjhcdWM3NDQgXHVkNTNjXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YWNjNFx1YzBiMFx1ZDU1Y1x1YjJlNC4gXHViMDk4XHViMjE3XHVjMTQ4XHVjNzU4IFx1ZDUzY1x1YzVmMFx1YzBiMFx1Yzc5MFx1YzVkMCBcdWM3NGNcdWMyMThcdWFjMDAgXHVjNzg4XHVjNzQ0IFx1YjU0Y1x1YjI5NCwgXHVhZGY4IFx1YzIxOFx1Yjk3YyBcdWM4MDhcdWIzMDBcdWFjMTJcdWM3NDQgXHVjNTBjXHVjNmI0IFx1YjRhNCBcdWFjYzRcdWMwYjBcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWIwOThcdWMxMWMgXHViYWFiXHVhY2ZjIFx1YjA5OFx1YmEzOFx1YzljMFx1Yzc1OCBcdWJkODBcdWQ2MzhcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWFjYjBcdWM4MTVcdWQ1NWNcdWIyZTQuIFx1ZDUzY1x1YzVmMFx1YzBiMFx1Yzc5MFx1YzkxMSBcdWM3NGNcdWMyMThcdWFjMDAgXHVkNTVjIFx1YWMxY1x1Yzc3Y1x1YjU0Y1x1YjI5NCBcdWJhYWJcdWM3NTggXHViZDgwXHVkNjM4XHVhYzAwIFx1Yzc0Y1x1YzIxOFx1Yzc3NFx1YjJlNC4gXHVjNzc0IFx1YWNiZFx1YzZiMFx1Yjk3YyBcdWM4MWNcdWM2NzhcdWQ1NThcdWJhNzQgXHViYWFiXHVjNzU4IFx1YmQ4MFx1ZDYzOFx1YjI5NCBcdWQ1NmRcdWMwYzEgXHVjNTkxXHVjMjE4XHVjNzc0XHViMmU0LiBcdWIwOThcdWJhMzhcdWM5YzBcdWM3NTggXHViZDgwXHVkNjM4XHViMjk0IFx1ZDUzY1x1YzgxY1x1YzIxOFx1Yzc1OCBcdWJkODBcdWQ2MzhcdWM2NDAgXHVhYzE5XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIDEzIGRpdiAtNCA9IC0zLCAtMTMgbW9kIDQgPSAtMSwgLTEzIG1vZCAtNCA9IC0xXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YTggXHVjNWQwXHViN2VjXHVhYzAwIFx1YmMxY1x1YzBkZFx1ZDU4OFx1Yzc0NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQsIFx1ZDYwNFx1YzdhYyBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NTggXHVjMjE4XHVkNTg5XHVjNzQ0IFx1YmE0OFx1Y2Q5NFx1YWNlMCwgXHVhZGY4IFx1YjJlNFx1Yzc0YyBcdWM1YjRcdWI1YTQgXHViYTg1XHViODM5XHViM2M0IFx1YzIxOFx1ZDU4OVx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVhZTMwXHVhY2M0IFx1YzVlY1x1YjdlYyBcdWIzMDBcdWM3NTggXHVjMTI0XHViYTg1XHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWFlMzBcdWFjYzRcdWM3NTggXHVjMTI0XHViYTg1XHVjNzQwIFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1YWNmYyBcdWM3ODVcdWI4MjVcdWM2MDFcdWM1ZWRcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA0XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQwIFx1YmE4NVx1YjgzOVx1YzViNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWJhODVcdWI4MzlcdWM1YjRcdWIyOTQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjNzg4XHViMmU0LiBcdWFjMDEgXHViYTg1XHViODM5XHVjNzQwIFx1YmIzOFx1YzgxYyBcdWMxMjRcdWJhODVcdWM1ZDAgXHViMDk4XHVjNjQwXHVjNzg4XHViMjk0IFx1YjMwMFx1YmIzOFx1Yzc5MCBcdWM1NGNcdWQzMGNcdWJjYjMgM1x1YWUwMFx1Yzc5MFx1Yzc3NFx1YWNlMCwgXHViMmU0XHViOTc4IFx1YWUwMFx1Yzc5MFx1YjI5NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBOVU1cdWM3NTggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YmE4NVx1YjgzOVx1YzViNCBcdWIyZTRcdWM3NGNcdWM1ZDAgXHVjMjJiXHVjNzkwXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHVjNzc0IFx1YzIyYlx1Yzc5MFx1YjI5NCAwXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWFjZTAsIDEwPHN1cD45PFwvc3VwPlx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC4gTlVNXHVhY2ZjIFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0MCBFTkRcdWFjMDAgXHViMDk4XHVjNjI0XHViYTc0IFx1YjA1ZFx1YjA5Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNjAxXHVjNWVkXHVjNzQwIFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4IFx1YzIxOFx1ZDU4OSBcdWQ2OWZcdWMyMTggTlx1Yzc3NCBcdWM3ODhcdWIyZTQuICgwICZsZTsgTiAmbGU7IDEwLDAwMCkgXHViMmU0XHVjNzRjIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1Yzc4NVx1YjgyNVx1YWMxMiBWPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM3ODhcdWIyZTQuICgwICZsZTsgVjxzdWI+aTxcL3N1Yj4gJmxlOyAxMDxzdXA+OTxcL3N1cD4pIFx1YWMwMSBcdWM3ODVcdWI4MjVcdWFjMTJcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWQ1NWMgXHViYzg4XHVjNTI5IFx1YzIxOFx1ZDU4OVx1ZDU3NFx1YzU3YyBcdWQ1NThcdWFjZTAsIFx1Yzc3NCBcdWMyMThcdWQ1ODlcdWM3NDAgXHViYWE4XHViNDUwIFx1YjNjNVx1YjliZFx1YzgwMVx1Yzc3NFx1YjJlNC4gXHViOWU0XHViYzg4IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWMyMThcdWQ1ODlcdWQ1NjAgXHViNTRjLCBcdWMyYTRcdWQwZGRcdWM1ZDAgXHViNGU0XHVjNWI0XHVjNzg4XHViMjk0IFx1YWMxMlx1Yzc0MCBcdWM3ODVcdWI4MjVcdWFjMTIgVjxzdWI+aTxcL3N1Yj4gXHVkNTU4XHViMDk4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVhZTMwXHVhY2M0IFx1YzEyNFx1YmE4NVx1Yzc0MCBcdWJlNDggXHVjOTA0XHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFFVSVRcdWM3NzQgXHViMDk4XHVjNjI0XHViYTc0IFx1YjJlNFx1Yzc0YyBcdWFlMzBcdWFjYzQgXHVjMTI0XHViYTg1XHVjNzc0IFx1YzVjNlx1YjJlNFx1YjI5NCBcdWI3M2JcdWM3NzRcdWIyZTQuIFx1YmE4NVx1YjgzOVx1YzViNFx1YWMwMCAxMDAsMDAwXHVhYzFjXHViOTdjIFx1YjExOFx1YzViNFx1YWMwMFx1YjI5NCBcdWFjYmRcdWM2YjBcdWM2NDAgXHVjMmE0XHVkMGRkXHVjNzc0IFx1YzIxOFx1ZDU4OVx1YjQyMCBcdWI1NGMsIDEsMDAwXHVhYzFjIFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWMyMmJcdWM3OTBcdWI5N2MgXHVjODAwXHVjN2E1XHVkNTU4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxXHVhYzAxXHVjNzU4IFx1Yzc4NVx1YjgyNVx1YWMxMlx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1ZDU3NFx1YjJmOVx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjMjE4XHVkNTg5XHVkNTVjIFx1YjRhNCwgXHVjZDljXHViODI1XHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuIFx1Y2Q5Y1x1YjgyNVx1YWMxMlx1Yzc3NFx1Yjc4MCBcdWMyYTRcdWQwZGRcdWM1ZDAgXHVjODAwXHVjN2E1XHViNDE4XHVjNWI0IFx1Yzc4OFx1YjI5NCBcdWMyMmJcdWM3OTBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjljY1x1YzU3ZCwgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4IFx1YzVkMFx1YjdlY1x1YWMwMCBcdWJjMWNcdWMwZGRcdWQ1NThcdWFjNzBcdWIwOTgsIFx1YmFhOFx1YjRlMCBcdWMyMThcdWQ1ODlcdWM3NzQgXHVjODg1XHViOGNjXHViNDEwXHVjNzQ0IFx1YjU0YyBcdWMyYTRcdWQwZGRcdWM1ZDAgXHVjODAwXHVjN2E1XHViNDE4XHVjNWI0IFx1Yzc4OFx1YjI5NCBcdWMyMmJcdWM3OTBcdWFjMDAgMVx1YWMxY1x1YWMwMCBcdWM1NDRcdWIyYzhcdWI3N2NcdWJhNzQsICZxdW90O0VSUk9SJnF1b3Q7XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1YWUzMFx1YWNjNFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjZDljXHViODI1XHVhYzEyXHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWNkOWNcdWI4MjVcdWQ1NWMgXHViNGE0XHVjNWQwXHViMjk0IFx1YmU0OCBcdWM5MDRcdWM3NDQgXHVkNTU4XHViMDk4IFx1Y2Q5Y1x1YjgyNVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzQyNSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlN0YWNrIE1hY2hpbmUgRXhlY3V0b3IiLCJkZXNjcmlwdGlvbiI6IjxwPk1hbnkgY2lwaGVycyBjYW4gYmUgY29tcHV0ZWQgbXVjaCBmYXN0ZXIgdXNpbmcgdmFyaW91cyBtYWNoaW5lcyBhbmQgYXV0b21hdGEuIEluIHRoaXMgcHJvYmxlbSwgd2Ugd2lsbCBmb2N1cyBvbiBvbmUgcGFydGljdWxhciB0eXBlIG9mIG1hY2hpbmVzIGNhbGxlZCBzdGFjayBtYWNoaW5lLiBJdHMgbmFtZSBjb21lcyBmcm9tIHRoZSBmYWN0IHRoYXQgdGhlIG1hY2hpbmUgb3BlcmF0ZXMgd2l0aCB0aGUgd2VsbC1rbm93biBkYXRhIHN0cnVjdHVyZSAmbWRhc2g7IHN0YWNrLiBUaGUgbGF0ZXItc3RvcmVkIHZhbHVlcyBhcmUgb24gdGhlIHRvcCwgb2xkZXIgdmFsdWVzIGF0IHRoZSBib3R0b20uIE1hY2hpbmUgaW5zdHJ1Y3Rpb25zIHR5cGljYWxseSBtYW5pcHVsYXRlIHRoZSB0b3Agb2YgdGhlIHN0YWNrIG9ubHkuPFwvcD5cclxuXHJcbjxwPk91ciBzdGFjayBtYWNoaW5lIGlzIHJlbGF0aXZlbHkgc2ltcGxlOiBJdCB3b3JrcyB3aXRoIGludGVnZXIgbnVtYmVycyBvbmx5LCBpdCBoYXMgbm8gc3RvcmFnZSBiZXNpZGUgdGhlIHN0YWNrIChubyByZWdpc3RlcnMgZXRjLikgYW5kIG5vIHNwZWNpYWwgaW5wdXQgb3Igb3V0cHV0IGRldmljZXMuIFRoZSBzZXQgb2YgaW5zdHJ1Y3Rpb25zIGlzIGFzIGZvbGxvd3M6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+PHN0cm9uZz5OVU0gWDxcL3N0cm9uZz4sIHdoZXJlIFggaXMgYSBub24tbmVnYXRpdmUgaW50ZWdlciBudW1iZXIsIDAgJmxlOyBYICZsZTsgMTA8c3VwPjk8XC9zdXA+LiBUaGUgTlVNIGluc3RydWN0aW9uIHN0b3JlcyB0aGUgbnVtYmVyIFggb24gdG9wIG9mIHRoZSBzdGFjay4gSXQgaXMgdGhlIG9ubHkgcGFyYW1ldHJpemVkIGluc3RydWN0aW9uLjxcL2xpPlxyXG5cdDxsaT48c3Ryb25nPlBPUDxcL3N0cm9uZz46IHJlbW92ZXMgdGhlIHRvcCBudW1iZXIgZnJvbSB0aGUgc3RhY2suPFwvbGk+XHJcblx0PGxpPjxzdHJvbmc+SU5WPFwvc3Ryb25nPjogY2hhbmdlcyB0aGUgc2lnbiBvZiB0aGUgdG9wLW1vc3QgbnVtYmVyLiAoNDIgJnJhcnI7ICZtaW51czs0Mik8XC9saT5cclxuXHQ8bGk+PHN0cm9uZz5EVVA8XC9zdHJvbmc+OiBkdXBsaWNhdGVzIHRoZSB0b3AtbW9zdCBudW1iZXIgb24gdGhlIHN0YWNrLjxcL2xpPlxyXG5cdDxsaT48c3Ryb25nPlNXUDxcL3N0cm9uZz46IHN3YXBzIChleGNoYW5nZXMpIHRoZSBwb3NpdGlvbiBvZiB0d28gdG9wLW1vc3QgbnVtYmVycy48XC9saT5cclxuXHQ8bGk+PHN0cm9uZz5BREQ8XC9zdHJvbmc+OiBhZGRzIHR3byBudW1iZXJzIG9uIHRoZSB0b3Agb2YgdGhlIHN0YWNrLjxcL2xpPlxyXG5cdDxsaT48c3Ryb25nPlNVQjxcL3N0cm9uZz46IHN1YnRyYWN0cyB0aGUgdG9wLW1vc3QgbnVtYmVyIGZyb20gdGhlICZsZHF1bztzZWNvbmQgb25lJnJkcXVvOyAodGhlIG9uZSBiZWxvdykuPFwvbGk+XHJcblx0PGxpPjxzdHJvbmc+TVVMPFwvc3Ryb25nPjogbXVsdGlwbGllcyB0d28gbnVtYmVycyBvbiB0aGUgdG9wIG9mIHRoZSBzdGFjay48XC9saT5cclxuXHQ8bGk+PHN0cm9uZz5ESVY8XC9zdHJvbmc+OiBpbnRlZ2VyIGRpdmlzb24gb2YgdHdvIG51bWJlcnMgb24gdGhlIHRvcC4gVGhlIHRvcC1tb3N0IG51bWJlciBiZWNvbWVzIGRpdmlzb3IsIHRoZSBvbmUgYmVsb3cgZGl2aWRlbmQuIFRoZSBxdW90aWVudCB3aWxsIGJlIHN0b3JlZCBhcyB0aGUgcmVzdWx0LjxcL2xpPlxyXG5cdDxsaT48c3Ryb25nPk1PRDxcL3N0cm9uZz46IG1vZHVsbyBvcGVyYXRpb24uIFRoZSBvcGVyYW5kcyBhcmUgdGhlIHNhbWUgYXMgZm9yIHRoZSBkaXZpc2lvbiBidXQgdGhlIHJlbWFpbmRlciBpcyBzdG9yZWQgYXMgdGhlIHJlc3VsdC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3N0bWMucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTAwcHg7IG9wYWNpdHk6MC45OyB3aWR0aDo1MTRweFwiIFwvPjxcL3A+XHJcblxyXG48cD5BbGwgYmluYXJ5IG9wZXJhdGlvbnMgY29uc2lkZXIgdGhlIHRvcC1tb3N0IG51bWJlciB0byBiZSB0aGUgJmxkcXVvO3JpZ2h0JnJkcXVvOyBvcGVyYW5kLCB0aGUgc2Vjb25kIG51bWJlciB0aGUgJmxkcXVvO2xlZnQmcmRxdW87IG9uZS4gQWxsIG9mIHRoZW0gcmVtb3ZlIGJvdGggb3BlcmFuZHMgZnJvbSB0aGUgc3RhY2sgYW5kIHBsYWNlIHRoZSByZXN1bHQgb24gdG9wIGluIHBsYWNlIG9mIHRoZSBvcmlnaW5hbCBudW1iZXJzLjxcL3A+XHJcblxyXG48cD5JZiB0aGVyZSBhcmUgbm90IGVub3VnaCBudW1iZXJzIG9uIHRoZSBzdGFjayBmb3IgYW4gaW5zdHJ1Y3Rpb24gKG9uZSBvciB0d28pLCB0aGUgZXhlY3V0aW9uIG9mIHN1Y2ggYW4gaW5zdHJ1Y3Rpb24gd2lsbCByZXN1bHQgaW50byBhIHByb2dyYW0gZmFpbHVyZS4gQSBmYWlsdXJlIGFsc28gb2NjdXJzIGlmIGEgZGl2aXNvciBiZWNvbWVzIHplcm8gKGZvciBESVYgb3IgTU9EKSBvciBpZiB0aGUgcmVzdWx0IG9mIGFueSBvcGVyYXRpb24gc2hvdWxkIGJlIG1vcmUgdGhhbiAxMDxzdXA+OTxcL3N1cD4gaW4gYWJzb2x1dGUgdmFsdWUuIFRoaXMgbWVhbnMgdGhhdCB0aGUgbWFjaGluZSBvbmx5IG9wZXJhdGVzIHdpdGggbnVtYmVycyBiZXR3ZWVuICZtaW51czsxIDAwMCAwMDAgMDAwIGFuZCAxIDAwMCAwMDAgMDAwLCBpbmNsdXNpdmUuPFwvcD5cclxuXHJcbjxwPlRvIGF2b2lkIGFtYmlndWl0aWVzIHdoaWxlIHdvcmtpbmcgd2l0aCBuZWdhdGl2ZSBkaXZpc29ycyBhbmQgcmVtYWluZGVyczogSWYgc29tZSBvcGVyYW5kIG9mIGEgZGl2aXNpb24gb3BlcmF0aW9uIGlzIG5lZ2F0aXZlLCB0aGUgYWJzb2x1dGUgdmFsdWUgb2YgdGhlIHJlc3VsdCBzaG91bGQgYWx3YXlzIGJlIGNvbXB1dGVkIHdpdGggYWJzb2x1dGUgdmFsdWVzIG9mIG9wZXJhbmRzLCBhbmQgdGhlIHNpZ24gaXMgZGV0ZXJtaW5lZCBhcyBmb2xsb3dzOiBUaGUgcXVvdGllbnQgaXMgbmVnYXRpdmUgaWYgKGFuZCBvbmx5IGlmKSBleGFjdGx5IG9uZSBvZiB0aGUgb3BlcmFuZHMgaXMgbmVnYXRpdmUuIFRoZSByZW1haW5kZXIgaGFzIHRoZSBzYW1lIHNpZ24gYXMgdGhlIGRpdmlkZW5kLiBUaHVzLCAxMyBkaXYgJm1pbnVzOzQgPSAmbWludXM7MywgJm1pbnVzOzEzIG1vZCA0ID0gJm1pbnVzOzEsICZtaW51czsxMyBtb2QgJm1pbnVzOzQgPSAmbWludXM7MSwgZXRjPFwvcD5cclxuXHJcbjxwPklmIGEgZmFpbHVyZSBvY2N1cnMgZm9yIGFueSByZWFzb24sIHRoZSBtYWNoaW5lIHN0b3BzIHRoZSBleGVjdXRpb24gb2YgdGhlIGN1cnJlbnQgcHJvZ3JhbSBhbmQgbm8gb3RoZXIgaW5zdHJ1Y3Rpb25zIGFyZSBldmFsdWF0ZWQgaW4gdGhhdCBwcm9ncmFtIHJ1bi48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb250YWlucyBkZXNjcmlwdGlvbiBvZiBzZXZlcmFsIG1hY2hpbmVzLiBFYWNoIG1hY2hpbmUgaXMgZGVzY3JpYmVkIGJ5IHR3byBwYXJ0czogdGhlIHByb2dyYW0gYW5kIHRoZSBpbnB1dCBzZWN0aW9uLjxcL3A+XHJcblxyXG48cD5UaGUgcHJvZ3JhbSBpcyBnaXZlbiBieSBhIHNlcmllcyBvZiBpbnN0cnVjdGlvbnMsIG9uZSBwZXIgbGluZS4gRXZlcnkgaW5zdHJ1Y3Rpb24gaXMgZ2l2ZW4gYnkgdGhyZWUgdXBwZXJjYXNlIGxldHRlcnMgYW5kIHRoZXJlIG11c3Qgbm90IGJlIGFueSBvdGhlciBjaGFyYWN0ZXJzLiBUaGUgb25seSBleGNlcHRpb24gaXMgdGhlIE5VTSBpbnN0cnVjdGlvbiwgd2hpY2ggaGFzIGV4YWN0bHkgb25lIHNwYWNlIGFmdGVyIHRoZSB0aHJlZSBsZXR0ZXJzIGZvbGxvd2VkIGJ5IGEgbm9uLW5lZ2F0aXZlIGludGVnZXIgbnVtYmVyIGJldHdlZW4gMCBhbmQgMTA8c3VwPjk8XC9zdXA+LiBUaGUgb25seSBhbGxvd2VkIGluc3RydWN0aW9ucyBhcmUgdGhvc2UgZGVcdWZiMDFuZWQgYWJvdmUuIEVhY2ggcHJvZ3JhbSBpcyB0ZXJtaW5hdGVkIGJ5IGEgbGluZSBjb250YWluaW5nIHRoZSB3b3JkICZsZHF1bztFTkQmcmRxdW87IChhbmQgbm90aGluZyBlbHNlKS48XC9wPlxyXG5cclxuPHA+VGhlIGlucHV0IHNlY3Rpb24gc3RhcnRzIHdpdGggYW4gaW50ZWdlciBOICgwICZsZTsgTiAmbGU7IDEwIDAwMCksIHRoZSBudW1iZXIgb2YgcHJvZ3JhbSBleGVjdXRpb25zLiBUaGUgbmV4dCBOIGxpbmVzIGNvbnRhaW4gb25lIG51bWJlciBlYWNoLCBzcGVjaWZ5aW5nIGFuIGlucHV0IHZhbHVlIFY8c3ViPmk8XC9zdWI+LCAwICZsZTsgVjxzdWI+aTxcL3N1Yj4gJmxlOyAxMDxzdXA+OTxcL3N1cD4uIFRoZSBwcm9ncmFtIHNob3VsZCBiZSBleGVjdXRlZCBvbmNlIGZvciBlYWNoIG9mIHRoZXNlIHZhbHVlcyBpbmRlcGVuZGVudGx5LCBldmVyeSBleGVjdXRpb24gc3RhcnRpbmcgd2l0aCB0aGUgc3RhY2sgY29udGFpbmluZyBvbmUgbnVtYmVyICZtZGFzaDsgdGhlIGlucHV0IHZhbHVlIFY8c3ViPmk8XC9zdWI+LjxcL3A+XHJcblxyXG48cD5UaGVyZSBpcyBvbmUgZW1wdHkgbGluZSBhdCB0aGUgYW5kIG9mIGVhY2ggbWFjaGluZSBkZXNjcmlwdGlvbi4gVGhlIGxhc3QgbWFjaGluZSBpcyBmb2xsb3dlZCBieSBhIGxpbmUgY29udGFpbmluZyB0aGUgd29yZCAmbGRxdW87UVVJVCZyZHF1bzsuIE5vIHByb2dyYW0gd2lsbCBjb250YWluIG1vcmUgdGhhbiAxMDAgMDAwIGluc3RydWN0aW9ucyBhbmQgbm8gcHJvZ3JhbSByZXF1aXJlcyBtb3JlIHRoYW4gMSAwMDAgbnVtYmVycyBvbiB0aGUgc3RhY2sgaW4gYW55IG1vbWVudCBkdXJpbmcgaXRzIGV4ZWN1dGlvbi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBpbnB1dCB2YWx1ZSwgcHJpbnQgb25lIGxpbmUgY29udGFpbmluZyB0aGUgb3V0cHV0IHZhbHVlIGZvciB0aGUgY29ycmVzcG9uZGluZyBleGVjdXRpb24sIGkuZS4sIHRoZSBvbmUgbnVtYmVyIHRoYXQgd2lsbCBiZSBvbiB0aGUgc3RhY2sgYWZ0ZXIgdGhlIHByb2dyYW0gZXhlY3V0ZXMgd2l0aCB0aGUgaW5pdGlhbCBzdGFjayBjb250YWluaW5nIG9ubHkgdGhlIGlucHV0IG51bWJlci48XC9wPlxyXG5cclxuPHA+SWYgdGhlcmUgaXMgYSBwcm9ncmFtIGZhaWx1cmUgZHVyaW5nIHRoZSBleGVjdXRpb24gb3IgaWYgdGhlIHN0YWNrIHNpemUgaXMgaW5jb3JyZWN0IGF0IHRoZSBlbmQgb2YgdGhlIHJ1biAoZWl0aGVyIGVtcHR5IG9yIHRoZXJlIGFyZSBtb3JlIG51bWJlcnMgdGhhbiBvbmUpLCBwcmludCB0aGUgd29yZCAmbGRxdW87RVJST1ImcmRxdW87IGluc3RlYWQuPFwvcD5cclxuXHJcbjxwPlByaW50IG9uZSBlbXB0eSBsaW5lIGFmdGVyIGVhY2ggbWFjaGluZSwgaW5jbHVkaW5nIHRoZSBsYXN0IG9uZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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

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