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

문제

무어 기계는 상태에 의해서 출력이 결정되는 유한 상태 기계이다. 무어 기계는 이름은 미국의 수학자이자 컴퓨터 과학자 Edward F. Moore의 이름을 따서 지었다. 무어 기계의 상태 전이는 입력에 의해서 정해진다. 예를 들어, 입력이 "aabba"이면, 아래와 같은 무어 기계의 출력은 "PRETTY"가 된다.

위의 그림에서 동그라미는 상태를 나타내고, 화살표 위의 글자는 입력 심볼을 나타낸다. 상태 중 하나는 시작 상태로 디자인 되어져 있다. 이 상태는 출발 노드가 없는 화살표로 나타나 있다. 이 경우에 시작 상태는 1번 상태이다. 상태 N과 출력 심볼 S는 N/S로 나타낸다.

대부분 경우에 무어 기계는 사이클을 가진다. 이 문제에서는 사이클이 전혀 없는 무어 기계를 다루며, 이런 종류의 기계를 직병렬 무어 기계라고 한다.

직병렬 무어 기계의 한 출력 심볼이 지워져 있다. 기계의 출력이 주어졌을 때, 지워진 심볼을 찾는 프로그램을 작성하시오. 항상 지워진 심볼을 찾을 수 있는 것은 아니다.

예를 들어, 아래 그림과 같은 직병렬 무어 기계가 있다.

위의 그림에는 상태를 간단하게 나타내기 위해 출력 심볼만 나타나 있다. 빈 원은 출력 심볼이 지워진 상태이다. 예를 들어, 기계의 출력이 "ADC"인 경우에는, 지워진 심볼이 D임을 알 수 있다. 하지만, 출력이 "ABC" 라면, 주어진 심볼을 유일하게 결정할 수 없다. "ABD"는 이 기계에서 나올 수 없는 출력이기 때문에, 불가능한 경우이다.

직병렬 무어 기계는 직병렬 그래프로 나타낼 수 있고, 간단히 표현할 수 있다. 상태가 하나이고, 출력이 S인 무어 기계는 'S' 로 나타낸다. 상태가 하나이고, 출력 심볼이 지워진 무어 기계는 '_'로 나타낸다. 여러 개의 부분 기계 M1, M2, ..., Mk가 직렬로 연결된 무어 기계는 M1M2...Mk로 나타낸다. 또, 부분 기계가 병렬로 연결된 무어 기계는 M1|M2|...|Mk로 나타낸다. 한 무어 기계가 더 큰 무어 기계의 일부로 사용된다면, 그 부분을 괄호로 감싼다. 이 방법을 사용하면, 위의 무어 기계는 A(B|_)C로 나타낼 수 있다.

직병렬 무어 기계와 그 기계의 출력이 주어졌을 때, 지워진 심볼을 구하는 프로그램을 작성하시오. 만약, 지워진 심볼을 유일하게 결정할 수 없다면, '_'를 출력한다. 또, 기계에서 나올 수 없는 출력이 주어진 경우에는 '!'를 출력한다.

입력

첫째 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 두 줄로 이루어져 있다. 첫째 줄에는 직병렬 무어 기계가 주어지고, 둘째 줄에는 기계의 출력이 주어진다. 출력 심볼은 알파벳 대문자로만 이루어져 있다. 무어 기계의 가장 바깥쪽 연결은 직렬이다. 또, 지워진 심볼의 개수는 하나이다. 각 줄의 길이는 100보다 작거나 같다.

출력

각 테스트 케이스마다, 지워진 심볼을 출력한다. 만약, 유일하게 결정할 수 없다면 '_'를 출력한다. 또, 입력으로 주어진 기계에서 만들 수 없는 경우에는 '!'를 출력한다.

예제 입력 1

3
A(B|_)C
ADC
A(B|D|_)C
ADC
A(B|CD(E|_)G)E
BOY

예제 출력 1

D
_
!
W3sicHJvYmxlbV9pZCI6IjMzMDAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJiMzRcdWM1YjQgXHVhZTMwXHVhY2M0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWJiMzRcdWM1YjQgXHVhZTMwXHVhY2M0XHViMjk0IFx1YzBjMVx1ZDBkY1x1YzVkMCBcdWM3NThcdWQ1NzRcdWMxMWMgXHVjZDljXHViODI1XHVjNzc0IFx1YWNiMFx1YzgxNVx1YjQxOFx1YjI5NCBcdWM3MjBcdWQ1NWMgXHVjMGMxXHVkMGRjIFx1YWUzMFx1YWNjNFx1Yzc3NFx1YjJlNC4gXHViYjM0XHVjNWI0IFx1YWUzMFx1YWNjNFx1YjI5NCBcdWM3NzRcdWI5ODRcdWM3NDAgXHViYmY4XHVhZDZkXHVjNzU4IFx1YzIxOFx1ZDU1OVx1Yzc5MFx1Yzc3NFx1Yzc5MCBcdWNlZjRcdWQ0ZThcdWQxMzAgXHVhY2ZjXHVkNTU5XHVjNzkwIEVkd2FyZCBGLiBNb29yZVx1Yzc1OCBcdWM3NzRcdWI5ODRcdWM3NDQgXHViNTMwXHVjMTFjIFx1YzljMFx1YzVjOFx1YjJlNC4gXHViYjM0XHVjNWI0IFx1YWUzMFx1YWNjNFx1Yzc1OCBcdWMwYzFcdWQwZGMgXHVjODA0XHVjNzc0XHViMjk0IFx1Yzc4NVx1YjgyNVx1YzVkMCBcdWM3NThcdWQ1NzRcdWMxMWMgXHVjODE1XHVkNTc0XHVjOWM0XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWM3ODVcdWI4MjVcdWM3NzQgJnF1b3Q7YWFiYmEmcXVvdDtcdWM3NzRcdWJhNzQsIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NDAgXHViYjM0XHVjNWI0IFx1YWUzMFx1YWNjNFx1Yzc1OCBcdWNkOWNcdWI4MjVcdWM3NDAgJnF1b3Q7UFJFVFRZJnF1b3Q7XHVhYzAwIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9tb29yZTEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTQ0cHg7IHdpZHRoOjQ2MXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzcwNFx1Yzc1OCBcdWFkZjhcdWI5YmNcdWM1ZDBcdWMxMWMgXHViM2Q5XHVhZGY4XHViNzdjXHViYmY4XHViMjk0IFx1YzBjMVx1ZDBkY1x1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWFjZTAsIFx1ZDY1NFx1YzBiNFx1ZDQ1YyBcdWM3MDRcdWM3NTggXHVhZTAwXHVjNzkwXHViMjk0IFx1Yzc4NVx1YjgyNSBcdWMyZWNcdWJjZmNcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWMwYzFcdWQwZGMgXHVjOTExIFx1ZDU1OFx1YjA5OFx1YjI5NCBcdWMyZGNcdWM3OTEgXHVjMGMxXHVkMGRjXHViODVjIFx1YjUxNFx1Yzc5MFx1Yzc3OCBcdWI0MThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVjMGMxXHVkMGRjXHViMjk0IFx1Y2Q5Y1x1YmMxYyBcdWIxNzhcdWI0ZGNcdWFjMDAgXHVjNWM2XHViMjk0IFx1ZDY1NFx1YzBiNFx1ZDQ1Y1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwOTggXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVhY2JkXHVjNmIwXHVjNWQwIFx1YzJkY1x1Yzc5MSBcdWMwYzFcdWQwZGNcdWIyOTQgMVx1YmM4OCBcdWMwYzFcdWQwZGNcdWM3NzRcdWIyZTQuIFx1YzBjMVx1ZDBkYyBOXHVhY2ZjIFx1Y2Q5Y1x1YjgyNSBcdWMyZWNcdWJjZmMgU1x1YjI5NCBOXC9TXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMzAwXHViZDgwXHViZDg0IFx1YWNiZFx1YzZiMFx1YzVkMCBcdWJiMzRcdWM1YjQgXHVhZTMwXHVhY2M0XHViMjk0IFx1YzBhY1x1Yzc3NFx1ZDA3NFx1Yzc0NCBcdWFjMDBcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWJiMzhcdWM4MWNcdWM1ZDBcdWMxMWNcdWIyOTQgXHVjMGFjXHVjNzc0XHVkMDc0XHVjNzc0IFx1YzgwNFx1ZDYwMCBcdWM1YzZcdWIyOTQgXHViYjM0XHVjNWI0IFx1YWUzMFx1YWNjNFx1Yjk3YyBcdWIyZTRcdWI4ZThcdWJhNzAsIFx1Yzc3NFx1YjdmMCBcdWM4ODVcdWI5NThcdWM3NTggXHVhZTMwXHVhY2M0XHViOTdjIFx1YzljMVx1YmNkMVx1YjgyYyBcdWJiMzRcdWM1YjQgXHVhZTMwXHVhY2M0XHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjOWMxXHViY2QxXHViODJjIFx1YmIzNFx1YzViNCBcdWFlMzBcdWFjYzRcdWM3NTggXHVkNTVjIFx1Y2Q5Y1x1YjgyNSBcdWMyZWNcdWJjZmNcdWM3NzQgXHVjOWMwXHVjNmNjXHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhZTMwXHVhY2M0XHVjNzU4IFx1Y2Q5Y1x1YjgyNVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM5YzBcdWM2Y2NcdWM5YzQgXHVjMmVjXHViY2ZjXHVjNzQ0IFx1Y2MzZVx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWQ1NmRcdWMwYzEgXHVjOWMwXHVjNmNjXHVjOWM0IFx1YzJlY1x1YmNmY1x1Yzc0NCBcdWNjM2VcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjODNcdWM3NDAgXHVjNTQ0XHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWM5YzFcdWJjZDFcdWI4MmMgXHViYjM0XHVjNWI0IFx1YWUzMFx1YWNjNFx1YWMwMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvbW9vcmUyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE0MHB4OyB3aWR0aDoyNzhweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM3MDRcdWM3NTggXHVhZGY4XHViOWJjXHVjNWQwXHViMjk0IFx1YzBjMVx1ZDBkY1x1Yjk3YyBcdWFjMDRcdWIyZThcdWQ1NThcdWFjOGMgXHViMDk4XHVkMGMwXHViMGI0XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWNkOWNcdWI4MjUgXHVjMmVjXHViY2ZjXHViOWNjIFx1YjA5OFx1ZDBjMFx1YjA5OCBcdWM3ODhcdWIyZTQuIFx1YmU0OCBcdWM2ZDBcdWM3NDAgXHVjZDljXHViODI1IFx1YzJlY1x1YmNmY1x1Yzc3NCBcdWM5YzBcdWM2Y2NcdWM5YzQgXHVjMGMxXHVkMGRjXHVjNzc0XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWFlMzBcdWFjYzRcdWM3NTggXHVjZDljXHViODI1XHVjNzc0ICZxdW90O0FEQyZxdW90O1x1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQsIFx1YzljMFx1YzZjY1x1YzljNCBcdWMyZWNcdWJjZmNcdWM3NzQgRFx1Yzc4NFx1Yzc0NCBcdWM1NGMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWNkOWNcdWI4MjVcdWM3NzQgJnF1b3Q7QUJDJnF1b3Q7IFx1Yjc3Y1x1YmE3NCwgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YzJlY1x1YmNmY1x1Yzc0NCBcdWM3MjBcdWM3N2NcdWQ1NThcdWFjOGMgXHVhY2IwXHVjODE1XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyZTQuICZxdW90O0FCRCZxdW90O1x1YjI5NCBcdWM3NzQgXHVhZTMwXHVhY2M0XHVjNWQwXHVjMTFjIFx1YjA5OFx1YzYyYyBcdWMyMTggXHVjNWM2XHViMjk0IFx1Y2Q5Y1x1YjgyNVx1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YmQ4OFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWFjYmRcdWM2YjBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzljMVx1YmNkMVx1YjgyYyBcdWJiMzRcdWM1YjQgXHVhZTMwXHVhY2M0XHViMjk0IFx1YzljMVx1YmNkMVx1YjgyYyBcdWFkZjhcdWI3OThcdWQ1MDRcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWFjZTAsIFx1YWMwNFx1YjJlOFx1ZDc4OCBcdWQ0NWNcdWQ2MDRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjMGMxXHVkMGRjXHVhYzAwIFx1ZDU1OFx1YjA5OFx1Yzc3NFx1YWNlMCwgXHVjZDljXHViODI1XHVjNzc0IFNcdWM3NzggXHViYjM0XHVjNWI0IFx1YWUzMFx1YWNjNFx1YjI5NCAmIzM5O1MmIzM5OyBcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWMwYzFcdWQwZGNcdWFjMDAgXHVkNTU4XHViMDk4XHVjNzc0XHVhY2UwLCBcdWNkOWNcdWI4MjUgXHVjMmVjXHViY2ZjXHVjNzc0IFx1YzljMFx1YzZjY1x1YzljNCBcdWJiMzRcdWM1YjQgXHVhZTMwXHVhY2M0XHViMjk0ICYjMzk7XyYjMzk7XHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4gXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWJkODBcdWJkODQgXHVhZTMwXHVhY2M0IE08c3ViPjE8XC9zdWI+LCBNPHN1Yj4yPFwvc3ViPiwgLi4uLCBNPHN1Yj5rPFwvc3ViPlx1YWMwMCBcdWM5YzFcdWI4MmNcdWI4NWMgXHVjNWYwXHVhY2IwXHViNDFjIFx1YmIzNFx1YzViNCBcdWFlMzBcdWFjYzRcdWIyOTQgTTxzdWI+MTxcL3N1Yj5NPHN1Yj4yPFwvc3ViPi4uLk08c3ViPms8XC9zdWI+XHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4gXHViNjEwLCBcdWJkODBcdWJkODQgXHVhZTMwXHVhY2M0XHVhYzAwIFx1YmNkMVx1YjgyY1x1Yjg1YyBcdWM1ZjBcdWFjYjBcdWI0MWMgXHViYjM0XHVjNWI0IFx1YWUzMFx1YWNjNFx1YjI5NCBNPHN1Yj4xPFwvc3ViPnxNPHN1Yj4yPFwvc3ViPnwuLi58TTxzdWI+azxcL3N1Yj5cdWI4NWMgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWQ1NWMgXHViYjM0XHVjNWI0IFx1YWUzMFx1YWNjNFx1YWMwMCBcdWIzNTQgXHVkMDcwIFx1YmIzNFx1YzViNCBcdWFlMzBcdWFjYzRcdWM3NTggXHVjNzdjXHViZDgwXHViODVjIFx1YzBhY1x1YzZhOVx1YjQxY1x1YjJlNFx1YmE3NCwgXHVhZGY4IFx1YmQ4MFx1YmQ4NFx1Yzc0NCBcdWFkMDRcdWQ2MzhcdWI4NWMgXHVhYzEwXHVjMmZjXHViMmU0LiBcdWM3NzQgXHViYzI5XHViYzk1XHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU1OFx1YmE3NCwgXHVjNzA0XHVjNzU4IFx1YmIzNFx1YzViNCBcdWFlMzBcdWFjYzRcdWIyOTQgQShCfF8pQ1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjOWMxXHViY2QxXHViODJjIFx1YmIzNFx1YzViNCBcdWFlMzBcdWFjYzRcdWM2NDAgXHVhZGY4IFx1YWUzMFx1YWNjNFx1Yzc1OCBcdWNkOWNcdWI4MjVcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjOWMwXHVjNmNjXHVjOWM0IFx1YzJlY1x1YmNmY1x1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHViOWNjXHVjNTdkLCBcdWM5YzBcdWM2Y2NcdWM5YzQgXHVjMmVjXHViY2ZjXHVjNzQ0IFx1YzcyMFx1Yzc3Y1x1ZDU1OFx1YWM4YyBcdWFjYjBcdWM4MTVcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNFx1YmE3NCwgJiMzOTtfJiMzOTtcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI2MTAsIFx1YWUzMFx1YWNjNFx1YzVkMFx1YzExYyBcdWIwOThcdWM2MmMgXHVjMjE4IFx1YzVjNlx1YjI5NCBcdWNkOWNcdWI4MjVcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCAmIzM5OyEmIzM5O1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWI0NTAgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjOWMxXHViY2QxXHViODJjIFx1YmIzNFx1YzViNCBcdWFlMzBcdWFjYzRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHVhY2UwLCBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWUzMFx1YWNjNFx1Yzc1OCBcdWNkOWNcdWI4MjVcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWNkOWNcdWI4MjUgXHVjMmVjXHViY2ZjXHVjNzQwIFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWIzMDBcdWJiMzhcdWM3OTBcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHViYjM0XHVjNWI0IFx1YWUzMFx1YWNjNFx1Yzc1OCBcdWFjMDBcdWM3YTUgXHViYzE0XHVhZTY1XHVjYWJkIFx1YzVmMFx1YWNiMFx1Yzc0MCBcdWM5YzFcdWI4MmNcdWM3NzRcdWIyZTQuIFx1YjYxMCwgXHVjOWMwXHVjNmNjXHVjOWM0IFx1YzJlY1x1YmNmY1x1Yzc1OCBcdWFjMWNcdWMyMThcdWIyOTQgXHVkNTU4XHViMDk4XHVjNzc0XHViMmU0LiBcdWFjMDEgXHVjOTA0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCAxMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCwgXHVjOWMwXHVjNmNjXHVjOWM0IFx1YzJlY1x1YmNmY1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHVjNzIwXHVjNzdjXHVkNTU4XHVhYzhjIFx1YWNiMFx1YzgxNVx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0XHViYTc0ICYjMzk7XyYjMzk7XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViNjEwLCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YWUzMFx1YWNjNFx1YzVkMFx1YzExYyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1YzVjNlx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgJiMzOTshJiMzOTtcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjMzMDAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJNb29yZSBNYWNoaW5lIiwiZGVzY3JpcHRpb24iOiI8cD5Nb29yZSBNYWNoaW5lIGlzIGEgZmluaXRlIHN0YXRlIG1hY2hpbmUgb2Ygd2hpY2ggdGhlIG91dHB1dCBpcyBkZXRlcm1pbmVkIGJ5IHRoZSBzdGF0ZXMgb2YgdGhlbS4gVGhlIE1vb3JlIE1hY2hpbmUgaXMgbmFtZWQgYWZ0ZXIgRWR3YXJkIEYuIE1vb3JlLCBhbiBBbWVyaWNhbiBtYXRoZW1hdGljaWFuIGFuZCBjb21wdXRlciBzY2llbnRpc3QuIFRoZSBzdGF0ZSB0cmFuc2l0aW9uIG9mIGEgTW9vcmUgTWFjaGluZSBpcyBkaXJlY3RlZCBieSB0aGUgZ2l2ZW4gaW5wdXQuIEZvciBleGFtcGxlLCBpZiB0aGUgaW5wdXQgaXMgZ2l2ZW4gYXMgJmxkcXVvO2FhYmJhLCZyZHF1bzsgdGhlIG91dHB1dCBvZiB0aGUgZm9sbG93aW5nIE1vb3JlIE1hY2hpbmUgaXMgJmxkcXVvO1BSRVRUWS4mcmRxdW87Jm5ic3A7PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvbW9vcmUxLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE0NHB4OyB3aWR0aDo0NjFweFwiIFwvPjxcL3A+XHJcblxyXG48cD5GaWd1cmUgMS4gQW4gZXhhbXBsZSBvZiBhIE1vb3JlIE1hY2hpbmU8XC9wPlxyXG5cclxuPHA+SW4gRmlndXJlIDEsIGEgY2lyY2xlIGRlbm90ZXMgZWFjaCBzdGF0ZSBhbmQgdGhlIGxhYmVsIG9uIHRoZSBhcnJvdyBkZW5vdGVzIHRoZSBpbnB1dCBzeW1ib2wuIE9uZSBvZiB0aGUgc3RhdGVzIGlzIGRlc2lnbmF0ZWQgYXMgdGhlIHN0YXJ0IHN0YXRlLCB3aGljaCBpcyByZXByZXNlbnRlZCBieSBhbiBhcnJvdyB3aXRoIG5vIG9yaWdpbiBwb2ludGluZyB0byB0aGUgc3RhdGUuIEluIHRoaXMgY2FzZSwgdGhlIHN0YXJ0IHN0YXRlIGlzIFN0YXRlIDEuIEVhY2ggc3RhdGUgTiB3aXRoIG91dHB1dCBzeW1ib2wgUyBpcyBkZXBpY3RlZCBpbiBsYWJlbCBOXC9TLiZuYnNwOzxcL3A+XHJcblxyXG48cD5HZW5lcmFsbHksIGEgTW9vcmUgTWFjaGluZSBjYW4gaGF2ZSBjeWNsZXMuIEhvd2V2ZXIsIHdlIGNhbiB0aGluayBvZiBhIGNlcnRhaW4ga2luZCBvZiBNb29yZSBNYWNoaW5lIHdoaWNoIGhhcyBubyBjeWNsZSBhdCBhbGwuIExldCZyc3F1bztzIGNhbGwgdGhpcyBraW5kIG9mIE1vb3JlIE1hY2hpbmUgYSBzZXJpZXMtcGFyYWxsZWwgTW9vcmUgTWFjaGluZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VW5mb3J0dW5hdGVseSwgb25lIG9mIHRoZSBvdXRwdXQgc3ltYm9scyBvZiBhIHNlcmllcy1wYXJhbGxlbCBNb29yZSBNYWNoaW5lIGlzIGVyYXNlZC4gVGhlIHByb2JsZW0gaXMgdG8gZmluZCB0aGUgZXJhc2VkIG91dHB1dCBzeW1ib2wgdXNpbmcgdGhlIGdpdmVuIG91dHB1dCBvZiB0aGUgbWFjaGluZS4gTm90ZSB0aGF0IGl0IGlzIG5vdCBhbHdheXMgcG9zc2libGUgdG8gZmluZCB0aGUgZXJhc2VkIHN5bWJvbC4gRm9yIGV4YW1wbGUsIGFzc3VtZSB0aGUgZm9sbG93aW5nIHNlcmllcy1wYXJhbGxlbCBNb29yZSBNYWNoaW5lIGlzIGdpdmVuLiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL21vb3JlMi5wbmdcIiBzdHlsZT1cImhlaWdodDoxNDBweDsgd2lkdGg6Mjc4cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+RmlndXJlIDIuIEFuIGV4YW1wbGUgb2YgYSBzZXJpZXMtcGFyYWxsZWwgTW9vcmUgTWFjaGluZTxcL3A+XHJcblxyXG48cD5JbiBGaWd1cmUgMiwgb25seSB0aGUgb3V0cHV0IHN5bWJvbHMgYXJlIHNob3duIGFzIGxhYmVscyBvbiBzdGF0ZXMgZm9yIHNpbXBsaWNpdHkuIFRoZSB3aGl0ZSBjaXJjbGUgd2l0aG91dCBhbnkgbGFiZWwgZGVub3RlcyB0aGUgc3RhdGUgd2hvc2Ugb3V0cHV0IHN5bWJvbCBpcyBlcmFzZWQuIElmIHRoZSBnaXZlbiBvdXRwdXQgb2YgdGhlIG1hY2hpbmUgaXMgJmxkcXVvO0FEQywmcmRxdW87IHRoZW4gd2UgY2FuIGRldGVybWluZSB0aGUgZXJhc2VkIHN5bWJvbCBpcyBELiBIb3dldmVyLCBpZiB0aGUgb3V0cHV0IGlzICZsZHF1bztBQkMsJnJkcXVvOyB3ZSBjYW5ub3QgdW5pcXVlbHkgZGV0ZXJtaW5lIHRoZSBlcmFzZWQgc3ltYm9sLiBPciwgaWYgdGhlIG91dHB1dCBpcyBnaXZlbiBhcyAmbGRxdW87QUJELCZyZHF1bzsgaXQgaXMgbm90IGEgdmFsaWQgb3V0cHV0IG9mIHRoaXMgbWFjaGluZS4gWW91ciBwcm9ncmFtIHNob3VsZCBhbHNvIGRldGVybWluZSB0aGVzZSBpbXBvc3NpYmxlIGNhc2VzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5TaW5jZSB0aGUgTW9vcmUgTWFjaGluZSBpcyByZWR1Y2VkIHRvIGEgc2VyaWVzLXBhcmFsbGVsIGdyYXBoLCB0aGUgcmVwcmVzZW50YXRpb24gb2YgdGhlIG1hY2hpbmUgaXRzZWxmIGNhbiBiZSBkZWZpbmVkIGluIGEgc3RyYWlnaHQtZm9yd2FyZCB3YXkuIEEgTW9vcmUgTWFjaGluZSBjb25zaXN0cyBvZiBhIHNpbmdsZSBzdGF0ZSwgd2hvc2Ugb3V0cHV0IGlzIFMsIGlzIGRlbm90ZWQgYnkgUyBpdHNlbGYuIEEgTW9vcmUgTWFjaGluZSBjb25zaXN0cyBvZiBhIHNpbmdsZSBzdGF0ZSwgd2hvc2Ugb3V0cHV0IHN5bWJvbCBpcyBlcmFzZWQsIGlzIGRlbm90ZWQgYnkgdGhlIHVuZGVyc2NvcmUgc3ltYm9sICZsc3F1bztfJnJzcXVvOy4gVGhlIE1vb3JlIE1hY2hpbmUgY29uc2lzdHMgb2YgYSBzZXJpZXMgb2Ygc3ViLW1hY2hpbmVzLCB3aG9zZSBkZXNjcmlwdGlvbnMgYXJlIE0xLCBNMiwgLi4uLCBhbmQgTWsgcmVzcGVjdGl2ZWx5LCBpcyBkZW5vdGVkIGJ5IE0xTTIuLi5NayBUaGUgTW9vcmUgTWFjaGluZSBjb25zaXN0cyBvZiBhIHBhcmFsbGVsIGNvbm5lY3Rpb24gc3ViLW1hY2hpbmVzLCB3aG9zZSBkZXNjcmlwdGlvbnMgYXJlIE0xLCBNMiwgLi4uLCBhbmQgTWsgcmVzcGVjdGl2ZWx5LCBpcyBkZW5vdGVkIGJ5IE0xfE0yfC4uLnxNay4gSWYgYSBNb29yZSBNYWNoaW5lIGlzIHVzZWQgYXMgYSBwYXJ0IG9mIGFub3RoZXIgYmlnZ2VyIE1vb3JlIE1hY2hpbmUsIHRoZSBwYXJlbnRoZXNlcyBjYW4gYmUgdXNlZCBmb3IgZW5jbG9zaW5nIHRoZSBwYXJ0LiBVc2luZyB0aGlzIHJlcHJlc2VudGF0aW9uLCB0aGUgYWJvdmUgTW9vcmUgTWFjaGluZSBjYW4gYmUgZ2l2ZW4gYXMgQShCfF8pQy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIGRldGVybWluaW5nIHRoZSBlcmFzZWQgc3ltYm9sIGZvciBhIGdpdmVuIHNlcmllcy1wYXJhbGxlbCBNb29yZSBNYWNoaW5lIGFuZCBhbiBvdXRwdXQgcHJvZHVjZWQgYnkgdGhlIG1hY2hpbmUuIElmIHRoZSBlcmFzZWQgc3ltYm9sIGNhbm5vdCBiZSB1bmlxdWVseSBkZXRlcm1pbmVkLCBwcmludCB0aGUgdW5kZXJzY29yZSBzeW1ib2wgJmxzcXVvO18mcnNxdW87IGluc3RlYWQuIElmIHRoZSBvdXRwdXQgY2Fubm90IGJlIHByb2R1Y2VkIGZyb20gdGhlIGdpdmVuIG1hY2hpbmUsIHByaW50IHRoZSBleGNsYW1hdGlvbiBtYXJrICZsc3F1bzshJnJzcXVvOyBpbnN0ZWFkLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHJlYWQgZnJvbSBzdGFuZGFyZCBpbnB1dC4gVGhlIGlucHV0IGNvbnNpc3RzIG9mIFQgdGVzdCBjYXNlcy4gVGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIFQgaXMgZ2l2ZW4gaW4gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0LiBGcm9tIHRoZSBzZWNvbmQgbGluZSwgZWFjaCB0ZXN0IGNhc2UgaXMgZ2l2ZW4uIEEgdGVzdCBjYXNlIGNvbnNpc3RzIG9mIHR3byBsaW5lcy4gVGhlIHN0cmluZyBpbiB0aGUgZmlyc3QgbGluZSBvZiBhIHRlc3QgY2FzZSBjb250YWlucyB0aGUgcmVwcmVzZW50YXRpb24gb2YgdGhlIHNlcmllcy1wYXJhbGxlbCBNb29yZSBNYWNoaW5lLiBUaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgYW4gb3V0cHV0IG9mIHRoZSBtYWNoaW5lLiBPbmx5IGNhcGl0YWwgRW5nbGlzaCBhbHBoYWJldHMgYXJlIHVzZWQgZm9yIHRoZSBvdXRwdXQgc3ltYm9scy4gSXQgaXMgYXNzdW1lZCB0aGF0IHRoZSBvdXRlcm1vc3QgY29ubmVjdGlvbiBvZiB0aGUgTW9vcmUgTWFjaGluZSBpcyBzZXJpYWwuIEl0IGlzIGFsc28gYXNzdW1lZCB0aGF0IHRoZXJlIGlzIG9ubHkgb25lIGVyYXNlZCBzeW1ib2wgaW4gdGhlIGlucHV0IG1hY2hpbmUuIFRoZSBsZW5ndGhzIG9mIHRoZSBpbnB1dCBsaW5lcyBvZiB0ZXN0IGNhc2VzIGFyZSBsZXNzIHRoYW4gb3IgZXF1YWwgdG8gMTAwLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQuIFByaW50IGV4YWN0bHkgb25lIGxpbmUgZm9yIGVhY2ggdGVzdCBjYXNlLiBUaGUgbGluZSBzaG91bGQgY29udGFpbiB0aGUgZXJhc2VkIG91dHB1dCBzeW1ib2wuIElmIGl0IGNhbm5vdCBiZSBkZXRlcm1pbmVkLCB0aGUgdW5kZXJzY29yZSBzeW1ib2wgc2hvdWxkIGJlIHByaW50ZWQuIElmIHRoZSBvdXRwdXQgY2Fubm90IGJlIHByb2R1Y2VkIGZyb20gdGhlIG1hY2hpbmUsIHRoZSBleGNsYW1hdGlvbiBtYXJrIHN5bWJvbCBzaG91bGQgYmUgcHJpbnRlZC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

ICPC > Regionals > Asia Pacific > Korea > Nationwide Internet Competition > Daejeon Nationalwide Internet Competition 2013 G번