시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 128 MB5010836.364%

문제

현종이는 공장 노동자이다. 부푼 꿈을 안고 입사해 20년간 일해왔으나, 만일 이번 달에 생산 효율이 증가하지 않는다면 다음 달에 해고될 것이라는 청천벽력같은 소식을 듣고 말았다. 현종이의 일은 간단하다. 주어진 순서대로 조각을 조립하여 제품을 제작하면 된다. 하지만 조각 a, b, c를 조립할 때, a-b 를 조립한 뒤 c를 이어붙이는 것과 b-c를 조립한 뒤 a를 이어붙이는 데에 걸리는 시간이 다르다. 현종이는 아마 이 공정을 효율적으로 개선하면 공장 일을 계속할 수 있을 것이라 판단했다.

현종이를 돕기 위해, 당신은 모든 조각을 조립하는 최적의 방법을 알려주는 프로그램을 작성하면 된다. 프로그램의 첫 줄에 조각의 목록이 주어진 뒤, 그 다음 줄부터 조각을 이어붙이는 데에 걸리는 시간과 그 결과물이 표 형태로 주어진다.

예제는 다음과 같다.

a와 a를 이어붙이는 데엔 3의 시간이 걸리고, 그 결과는 부품 b가 된다. 그리고 이것의 뒤에 다시 a를 이어붙이는 데엔 6의 시간이 걸릴 것이다. 표는 대칭이 아닐 수 있다. b-a를 조립하는 시간과 a-b를 조립하는 시간이 다를 수 있다는 의미이다.

만일 만들고자 하는 완성품이 aba라면, 두 가지 가능한 경우는 다음과 같다.

  • (ab)a = ba = a , 걸리는 시간 = time(ab) + time(ba) = 5 + 6 =11
  • a(ba) = aa = b , 걸리는 시간 = time(ba) + time(aa) = 6 + 3 = 9

따라서 출력은 9-b가 될 것이다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫 줄엔 자연수 k ( 1 ≤ k ≤ 26 ) 이 주어지며, 그 다음 줄엔 공백으로 구분되어 조각의 이름들이 주어진다. ( [a-z] 에 포함되는 알파벳 ).

다음 k개의 줄엔 생산 공정 표가 주어진다. 각 줄은 k개의 문자열로 이루어져 있으며, i행 j열의 값은 i번째 부품을 j번째 부품과 조립하는 데에 걸리는 시간과 결과물을 나타낸다. 조립에 걸리는 시간은 0 이상 1000000 이하의 정수이며, 결과물로 잘못된 문자가 주어지는 경우는 없다.

그 다음 줄엔 정수 n이 주어지며, 만들고자 하는 완성품의 개수이다.

다음 n줄엔 완성품의 형태가 주어진다.

각 완성품은 200개 이하의 부품으로 이루어져 있으며, 주어진 형태를 변경하여 조립할 수는 없다.

k=0일 경우 프로그램을 종료하며 이 경우엔 아무 것도 출력하지 않는다.

출력

각 테스트 케이스에 대해, 각 완성품을 가장 빨리 만들 수 있는 경우에 걸리는 시간과 그 때의 결과물을 time-result 의 형태로 한 줄에 하나씩 출력한다. 만일 그러한 것이 여러 가지라면 결과물이 처음 주어진 부품의 목록에서 더 먼저 등장한 것을 출력한다. 예를 들어, 결과로 5-b와 5-c가 가능하며, 테스트 케이스의 두 번째 줄에서 입력받은 부품의 목록이 a c b 였다면 5-c를 출력하면 된다.

각 테스트 케이스의 사이엔 빈 줄을 하나 출력한다.

예제 입력 1

2
a b
3-b 5-b
6-a 2-b
2
aba
bba
2
m e
5-e 4-m
3-e 4-m
1
eme
0

예제 출력 1

9-b
8-a

7-m
W3sicHJvYmxlbV9pZCI6IjM4NTIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwZGRcdWMwYjAgXHVhY2Y1XHVjODE1IiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ2MDRcdWM4ODVcdWM3NzRcdWIyOTQgXHVhY2Y1XHVjN2E1IFx1YjE3OFx1YjNkOVx1Yzc5MFx1Yzc3NFx1YjJlNC4gXHViZDgwXHVkNDdjIFx1YWZjOFx1Yzc0NCBcdWM1NDhcdWFjZTAgXHVjNzg1XHVjMGFjXHVkNTc0IDIwXHViMTQ0XHVhYzA0IFx1Yzc3Y1x1ZDU3NFx1YzY1NFx1YzczY1x1YjA5OCwgXHViOWNjXHVjNzdjIFx1Yzc3NFx1YmM4OCBcdWIyZWNcdWM1ZDAmbmJzcDtcdWMwZGRcdWMwYjAgXHVkNmE4XHVjNzI4XHVjNzc0IFx1Yzk5ZFx1YWMwMFx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTRcdWJhNzQgXHViMmU0XHVjNzRjIFx1YjJlY1x1YzVkMCBcdWQ1NzRcdWFjZTBcdWI0MjAgXHVhYzgzXHVjNzc0XHViNzdjXHViMjk0IFx1Y2NhZFx1Y2M5Y1x1YmNiZFx1YjgyNVx1YWMxOVx1Yzc0MCBcdWMxOGNcdWMyZGRcdWM3NDQgXHViNGUzXHVhY2UwIFx1YjlkMFx1YzU1OFx1YjJlNC4gXHVkNjA0XHVjODg1XHVjNzc0XHVjNzU4IFx1Yzc3Y1x1Yzc0MCBcdWFjMDRcdWIyZThcdWQ1NThcdWIyZTQuIFx1YzhmY1x1YzViNFx1YzljNCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjODcwXHVhYzAxXHVjNzQ0IFx1Yzg3MFx1YjliZFx1ZDU1OFx1YzVlYyBcdWM4MWNcdWQ0ODhcdWM3NDQgXHVjODFjXHVjNzkxXHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjIFx1Yzg3MFx1YWMwMSBhLCBiLCBjXHViOTdjIFx1Yzg3MFx1YjliZFx1ZDU2MCBcdWI1NGMsIGEtYiBcdWI5N2MgXHVjODcwXHViOWJkXHVkNTVjIFx1YjRhNCBjXHViOTdjIFx1Yzc3NFx1YzViNFx1YmQ5OVx1Yzc3NFx1YjI5NCBcdWFjODNcdWFjZmMgYi1jXHViOTdjIFx1Yzg3MFx1YjliZFx1ZDU1YyBcdWI0YTQgYVx1Yjk3YyBcdWM3NzRcdWM1YjRcdWJkOTlcdWM3NzRcdWIyOTQgXHViMzcwXHVjNWQwIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NzQgXHViMmU0XHViOTc0XHViMmU0LiBcdWQ2MDRcdWM4ODVcdWM3NzRcdWIyOTQmbmJzcDtcdWM1NDRcdWI5YzggXHVjNzc0IFx1YWNmNVx1YzgxNVx1Yzc0NCBcdWQ2YThcdWM3MjhcdWM4MDFcdWM3M2NcdWI4NWMgXHVhYzFjXHVjMTIwXHVkNTU4XHViYTc0IFx1YWNmNVx1YzdhNSBcdWM3N2NcdWM3NDQgXHVhY2M0XHVjMThkXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWM3NDQgXHVhYzgzXHVjNzc0XHViNzdjIFx1ZDMxMFx1YjJlOFx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNjA0XHVjODg1XHVjNzc0XHViOTdjIFx1YjNkNVx1YWUzMCBcdWM3MDRcdWQ1NzQsIFx1YjJmOVx1YzJlMFx1Yzc0MCBcdWJhYThcdWI0ZTAgXHVjODcwXHVhYzAxXHVjNzQ0IFx1Yzg3MFx1YjliZFx1ZDU1OFx1YjI5NCBcdWNkNWNcdWM4MDFcdWM3NTggXHViYzI5XHViYzk1XHVjNzQ0IFx1YzU0Y1x1YjgyNFx1YzhmY1x1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC4mbmJzcDtcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NTggXHVjY2FiIFx1YzkwNFx1YzVkMCBcdWM4NzBcdWFjMDFcdWM3NTggXHViYWE5XHViODVkXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNCBcdWI0YTQsIFx1YWRmOCBcdWIyZTRcdWM3NGMgXHVjOTA0XHViZDgwXHVkMTMwJm5ic3A7XHVjODcwXHVhYzAxXHVjNzQ0IFx1Yzc3NFx1YzViNFx1YmQ5OVx1Yzc3NFx1YjI5NCBcdWIzNzBcdWM1ZDAgXHVhYzc4XHViOWFjXHViMjk0IFx1YzJkY1x1YWMwNFx1YWNmYyBcdWFkZjggXHVhY2IwXHVhY2ZjXHViYjNjXHVjNzc0IFx1ZDQ1YyBcdWQ2MTVcdWQwZGNcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWM4MWNcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9hc3NlbWJsZS5wbmdcIiBcLz48XC9wPlxyXG5cclxuPHA+YVx1YzY0MCBhXHViOTdjIFx1Yzc3NFx1YzViNFx1YmQ5OVx1Yzc3NFx1YjI5NCBcdWIzNzBcdWM1ZDQgM1x1Yzc1OCBcdWMyZGNcdWFjMDRcdWM3NzQgXHVhYzc4XHViOWFjXHVhY2UwLCBcdWFkZjggXHVhY2IwXHVhY2ZjXHViMjk0IFx1YmQ4MFx1ZDQ4OCBiXHVhYzAwIFx1YjQxY1x1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwJm5ic3A7XHVjNzc0XHVhYzgzXHVjNzU4IFx1YjRhNFx1YzVkMCBcdWIyZTRcdWMyZGMgYVx1Yjk3YyBcdWM3NzRcdWM1YjRcdWJkOTlcdWM3NzRcdWIyOTQgXHViMzcwXHVjNWQ0IDZcdWM3NTggXHVjMmRjXHVhYzA0XHVjNzc0IFx1YWM3OFx1YjliNCBcdWFjODNcdWM3NzRcdWIyZTQuJm5ic3A7XHVkNDVjXHViMjk0IFx1YjMwMFx1Y2U2ZFx1Yzc3NCBcdWM1NDRcdWIyZDAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gYi1hXHViOTdjIFx1Yzg3MFx1YjliZFx1ZDU1OFx1YjI5NCBcdWMyZGNcdWFjMDRcdWFjZmMgYS1iXHViOTdjIFx1Yzg3MFx1YjliZFx1ZDU1OFx1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NzQgXHViMmU0XHViOTdjIFx1YzIxOCBcdWM3ODhcdWIyZTRcdWIyOTQgXHVjNzU4XHViYmY4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI5Y2NcdWM3N2MgXHViOWNjXHViNGU0XHVhY2UwXHVjNzkwIFx1ZDU1OFx1YjI5NCBcdWM2NDRcdWMxMzFcdWQ0ODhcdWM3NzQgYWJhXHViNzdjXHViYTc0LCBcdWI0NTAgXHVhYzAwXHVjOWMwIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWFjYmRcdWM2YjBcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4oYWIpYSA9IGJhID0gYSAsIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWMyZGNcdWFjMDQgPSB0aW1lKGFiKSArIHRpbWUoYmEpID0gNSArIDYgPTExPFwvbGk+XHJcblx0PGxpPmEoYmEpID0gYWEgPSBiJm5ic3A7LCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0ID0gdGltZShiYSkgKyB0aW1lKGFhKSA9IDYgKyAzID0gOTxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YjUzMFx1Yjc3Y1x1YzExYyBcdWNkOWNcdWI4MjVcdWM3NDAgOS1iXHVhYzAwIFx1YjQyMCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYiBcdWM5MDRcdWM1ZDQgXHVjNzkwXHVjNWYwXHVjMjE4IGsgKCAxJm5ic3A7JmxlOyBrJm5ic3A7JmxlOyAyNiApIFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1YWRmOCBcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQ0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjODcwXHVhYzAxXHVjNzU4IFx1Yzc3NFx1Yjk4NFx1YjRlNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICggW2Etel0gXHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YjI5NCBcdWM1NGNcdWQzMGNcdWJjYjMgKS48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIGtcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQ0IFx1YzBkZFx1YzBiMCBcdWFjZjVcdWM4MTUgXHVkNDVjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YzkwNFx1Yzc0MCBrXHVhYzFjXHVjNzU4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVjNzNjXHViYTcwLCBpXHVkNTg5IGpcdWM1ZjRcdWM3NTggXHVhYzEyXHVjNzQwIGlcdWJjODhcdWM5ZjggXHViZDgwXHVkNDg4XHVjNzQ0IGpcdWJjODhcdWM5ZjggXHViZDgwXHVkNDg4XHVhY2ZjIFx1Yzg3MFx1YjliZFx1ZDU1OFx1YjI5NCBcdWIzNzBcdWM1ZDAgXHVhYzc4XHViOWFjXHViMjk0IFx1YzJkY1x1YWMwNFx1YWNmYyBcdWFjYjBcdWFjZmNcdWJiM2NcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWM4NzBcdWI5YmRcdWM1ZDAgXHVhYzc4XHViOWFjXHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc0MCAwIFx1Yzc3NFx1YzBjMSAxMDAwMDAwIFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWM4MTVcdWMyMThcdWM3NzRcdWJhNzAsIFx1YWNiMFx1YWNmY1x1YmIzY1x1Yjg1YyBcdWM3OThcdWJhYmJcdWI0MWMgXHViYjM4XHVjNzkwXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkZjggXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkNCBcdWM4MTVcdWMyMTggblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1YjljY1x1YjRlNFx1YWNlMFx1Yzc5MCBcdWQ1NThcdWIyOTQgXHVjNjQ0XHVjMTMxXHVkNDg4XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIG5cdWM5MDRcdWM1ZDQgXHVjNjQ0XHVjMTMxXHVkNDg4XHVjNzU4IFx1ZDYxNVx1ZDBkY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSZuYnNwO1x1YzY0NFx1YzEzMVx1ZDQ4OFx1Yzc0MCAyMDBcdWFjMWMgXHVjNzc0XHVkNTU4XHVjNzU4IFx1YmQ4MFx1ZDQ4OFx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVjNzNjXHViYTcwLCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVkNjE1XHVkMGRjXHViOTdjIFx1YmNjMFx1YWNiZFx1ZDU1OFx1YzVlYyZuYnNwO1x1Yzg3MFx1YjliZFx1ZDU2MCBcdWMyMThcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5rPTBcdWM3N2MgXHVhY2JkXHVjNmIwIFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM4ODVcdWI4Y2NcdWQ1NThcdWJhNzAgXHVjNzc0IFx1YWNiZFx1YzZiMFx1YzVkNCBcdWM1NDRcdWJiMzQgXHVhYzgzXHViM2M0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0LCBcdWFjMDEgXHVjNjQ0XHVjMTMxXHVkNDg4XHVjNzQ0IFx1YWMwMFx1YzdhNSBcdWJlNjhcdWI5YWMgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNWQwIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWFjZmMgXHVhZGY4IFx1YjU0Y1x1Yzc1OCBcdWFjYjBcdWFjZmNcdWJiM2NcdWM3NDQgdGltZS1yZXN1bHQgXHVjNzU4IFx1ZDYxNVx1ZDBkY1x1Yjg1YyBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSZuYnNwO1x1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNzdjIFx1YWRmOFx1YjdlY1x1ZDU1YyBcdWFjODNcdWM3NzQgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMFx1Yjc3Y1x1YmE3NCBcdWFjYjBcdWFjZmNcdWJiM2NcdWM3NzQgXHVjYzk4XHVjNzRjIFx1YzhmY1x1YzViNFx1YzljNCBcdWJkODBcdWQ0ODhcdWM3NTggXHViYWE5XHViODVkXHVjNWQwXHVjMTFjIFx1YjM1NCBcdWJhM2NcdWM4MDAgXHViNGYxXHVjN2E1XHVkNTVjIFx1YWM4M1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YWNiMFx1YWNmY1x1Yjg1YyA1LWJcdWM2NDAgNS1jXHVhYzAwIFx1YWMwMFx1YjJhNVx1ZDU1OFx1YmE3MCwgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YzExYyBcdWM3ODVcdWI4MjVcdWJjMWJcdWM3NDAgXHViZDgwXHVkNDg4XHVjNzU4IFx1YmFhOVx1Yjg1ZFx1Yzc3NCBhIGMgYiBcdWM2MDBcdWIyZTRcdWJhNzQgNS1jXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YzBhY1x1Yzc3NFx1YzVkNCBcdWJlNDggXHVjOTA0XHVjNzQ0IFx1ZDU1OFx1YjA5OCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzg1MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkFzc2VtYmx5IGxpbmUiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBsYXN0IHdvcmtlciBpbiBhIHByb2R1Y3Rpb24gbGluZSBhdCB0aGUgZmFjdG9yeSBvZiBBdXRvbWF0ZWQgQ29tcG9zZWQgTWFjaGluZXJ5IGlzIHdvcnJpZWQuIFNoZSBrbm93cyB0aGF0IGhlciBqb2IgaGFuZ3MgaW4gdGhlIGJhbGFuY2UgdW5sZXNzIGhlciBwcm9kdWN0aXZpdHkgaW5jcmVhc2VzLiBIZXIgd29yayBjb25zaXN0cyBvZiBhc3NlbWJsaW5nIGEgc2V0IG9mIHBpZWNlcyBpbiBhIGdpdmVuIHNlcXVlbmNlLCBidXQgdGhlIHRpbWUgc3BlbnQgb24gYXNzZW1ibGluZyBwaWVjZXMgYSBhbmQgYiBhbmQgdGhlbiBjIG1heSBub3QgdGhlIHNhbWUgYXMgdGhhdCBvbiBhc3NlbWJsaW5nIHBpZWNlcyBiIGFuZCBjLCBhbmQgdGhlbiBhc3NlbWJsaW5nIGEgd2l0aCB0aGUgcmVzdWx0aW5nIGNvbXBvbmVudC4gT25seSB0d28gY29uc2VjdXRpdmUgcGllY2VzIG1heSBiZSBhc3NlbWJsZWQgYXQgYSB0aW1lLCBhbmQgb25jZSB0aGV5IGFyZSBhc3NlbWJsZWQgdGhleSBiZWhhdmUgYXMgYW5vdGhlciBwaWVjZSBpbiB0ZXJtcyBvZiB0aGUgdGltZSBuZWVkZWQgZm9yIGZ1cnRoZXIgYXNzZW1ibHkuPFwvcD5cclxuXHJcbjxwPkluIG9yZGVyIHRvIGFpZCBoZXIsIHlvdSBuZWVkIHRvIGZpbmQgdGhlIG9wdGltYWwgd2F5IHRvIGFzc2VtYmxlIGFsbCBjb21wb25lbnRzLiBUaGUgaW5wdXQgdG8geW91ciBwcm9ncmFtIHdpbGwgYmUgYSBzZXQgb2Ygc3ltYm9scyByZXByZXNlbnRpbmcgKHR5cGVzIG9mKSBwaWVjZXMsIGFuZCBhIHNvLWNhbGxlZCBhc3NlbWJseSB0YWJsZSByZXByZXNlbnRpbmcgdGhlIHRpbWUgaXQgdGFrZXMgdG8gYXNzZW1ibGUgdGhlbSwgYXMgd2VsbCBhcyB0aGUgdHlwZSBvZiB0aGUgcmVzdWx0aW5nIGNvbXBvbmVudC4gRm9yIGluc3RhbmNlLCB3ZSBtYXkgaGF2ZSB0d28gc3ltYm9scyB7YSwgYn0sIGFuZCB0aGUgZm9sbG93aW5nIHRhYmxlOjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2Fzc2VtYmxlLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjcwcHg7IHdpZHRoOjEwOXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlRoaXMgbWVhbnMsIGZvciBleGFtcGxlLCB0aGF0IHR3byBwaWVjZXMgb2YgdHlwZSBhIGFuZCBhIG1heSBhc3NlbWJsZWQgaW4gMyBtaW51dGVzLCBhbmQgdGhlIHJlc3VsdCBpcyBhIGNvbXBvbmVudCBvZiB0eXBlIGIsIGluIHRoYXQgdGhlIHRpbWUgcmVxdWlyZWQgdG8gYXNzZW1ibGUgaXQgYWdhaW4gd2l0aCBhbm90aGVyIHBpZWNlIG9mLCBzYXksIHR5cGUgYSBpcyA2IG1pbnV0ZXMsIGFuZCBzbyBvbi4gTm90ZSB0aGF0IHRoZSB0YWJsZSBpcyBub3Qgc3ltbWV0cmljLCBpLmUuIGFzc2VtYmxpbmcgYiBhbmQgYSBtYXkgYmUgbW9yZSB0aW1lLWNvbnN1bWluZyB0aGFuIGEgYW5kIGIuPFwvcD5cclxuXHJcbjxwPkZvciBhIHNlcXVlbmNlIG9mIGNvbXBvbmVudHMgbGFiZWxsZWQgYWJhLCB0aGUgdHdvIHBvc3NpYmxlIHNvbHV0aW9ucyBhcmU6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+KGFiKWEgPSBiYSA9IGEgd2l0aCB0aW1lIHRpbWUoYWIpICsgdGltZShiYSkgPSA1ICsgNiA9IDExLjxcL2xpPlxyXG5cdDxsaT5hKGJhKSA9IGFhID0gYiB3aXRoIHRpbWUgdGltZShiYSkgKyB0aW1lKGFhKSA9IDYgKyAzID0gOS48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5TbyB0aGUgcmVzdWx0IGZvciB0aGlzIGNhc2Ugd291bGQgYmUgYSBwaWVjZSBvZiB0eXBlIGIgaW4gOSBtaW51dGVzIChkZW5vdGVkIDktYikuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29uc2lzdHMgb2Ygc2V2ZXJhbCB0ZXN0IGNhc2VzLiBFYWNoIHRlc3QgY2FzZSBiZWdpbnMgd2l0aCBhIGxpbmUgY29udGFpbmluZyBhIG5hdHVyYWwgbnVtYmVyIGsgKDEgJmxlOyBrICZsZTsgMjYpLCBmb2xsb3dlZCBieSBhIGxpbmUgd2l0aCBrIHN5bWJvbHMgKGNoYXJhY3RlcnMgaW4gW2Etel0pIHNlcGFyYXRlZCBieSBzcGFjZXMuIFRoZSBmb2xsb3dpbmcgayBsaW5lcyBjb250YWluIHRoZSBhc3NlbWJseSB0YWJsZTogdGhlIGktdGggbGluZSBoYXMgayBwYWlycyBvZiB0aGUgZm9ybSB0aW1lLXJlc3VsdCwgd2hlcmUgdGltZSBpcyBhbiBpbnRlZ2VyIGJldHdlZW4gMCBhbmQgMSAwMDAgMDAwIGluY2x1c2l2ZSwgYW5kIHJlc3VsdCBhIHN5bWJvbCBiZWxvbmdpbmcgdG8gdGhlIHByZWNlZGluZyBzZXQuIFRoZSBqLXRoIHBhaXIgaW4gdGhlIGktdGggbGluZSByZXByZXNlbnRzIHRoZSB0aW1lIHRvIGNvbXBvc2UgcGllY2VzIG9mIHR5cGVzIHJlcHJlc2VudGVkIGJ5IHRoZSBpLXRoIGFuZCBqLXRoIHN5bWJvbHMsIGFsb25nIHdpdGggdGhlIHR5cGUgb2YgdGhlIHJlc3VsdGluZyBwaWVjZS4gQWZ0ZXIgdGhlIHRhYmxlLCBhIGxpbmUgd2l0aCBhbiBpbnRlZ2VyIG4gaW5kaWNhdGVzIHRoZSBudW1iZXIgb2YgbGluZXMgdGhhdCBmb2xsb3csIGVhY2ggbGluZSBiZWluZyBhIHN0cmluZyBvZiBhdCBtb3N0IDIwMCBzeW1ib2xzLiBFYWNoIG9mIHRoZXNlIGxpbmVzIGlzIGEgc2VxdWVuY2Ugb2YgY29tcG9uZW50cyB0aGF0IG5lZWQgdG8gYmUgYXNzZW1ibGVkIHRvZ2V0aGVyIGluIHRoZSByaWdodCBvcmRlci48XC9wPlxyXG5cclxuPHA+VGhlIGlucHV0IHdpbGwgZmluaXNoIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgMCwgd2hpY2ggc2hvdWxkIG5vdCBiZSBwcm9jZXNzZWQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBwcmludCBuIGxpbmVzLCBlYWNoIHdpdGggYW4gaW50ZWdlciB0aW1lIGFuZCBhIHN5bWJvbCByZXN1bHQgaW4gdGhlIGZvcm1hdCB0aW1lLXJlc3VsdC4gRWFjaCBsaW5lIHJlcHJlc2VudHMgdGhlIG1pbmltdW0gdGltZSBhbmQgdGhlIHR5cGUgb2YgdGhlIHJlc3VsdGluZyBwaWVjZSBmb3IgdGhlIGNvcnJlc3BvbmRpbmcgY2FzZSBpbiB0aGUgaW5wdXQuIEluIGNhc2Ugb2YgYSB0aWUgYW1vbmcgc2V2ZXJhbCBwb3NzaWJsZSByZXN1bHRzIHdpdGggdGhlIHNhbWUgbWluaW11bSB0aW1lLCBjaG9vc2UgZnJvbSBhbW9uZyB0aG9zZSB0aGUgcGllY2Ugd2hvc2UgdHlwZSBsZXR0ZXIgYXBwZWFycyBmaXJzdCBpbiB0aGUgbGluZSB0aGF0IGNvbnRhaW5lZCB0aGUgayBzeW1ib2xzIGF0IHRoZSBiZWdpbm5pbmcgb2YgdGhlIHRlc3QgY2FzZS4gKEZvciBleGFtcGxlLCBpZiB0aGF0IGxpbmUgd2FzIGEgYyBiIGFuZCBib3RoIGMgYW5kIGIgY2FuIGJlIG9idGFpbmVkIHdpdGggbWluaW11bSBjb3N0IDUsIHByaW50IDUtYykuPFwvcD5cclxuXHJcbjxwPlRoZXJlIG11c3QgYmUgYW4gZW1wdHkgbGluZSBiZXR3ZWVuIHRoZSBvdXRwdXQgb2YgZGlmZmVyZW50IHRlc3QgY2FzZXMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

ICPC > Regionals > Europe > Southwestern European Regional Contest > SWERC 2010 H번