시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 128 MB1492155.882%

문제

데이터를 압축하는 방법 중에서 상대적으로 간단한 방법은 허프만 트리를 이용하는 것이다. 허프만 트리를 이용하면 한 파일이 포함하고 있는 데이터를 압축하고 압축 해제하는 작업을 손쉽게 할 수 있다. 많은 응용프로그램은 바이너리 허프만 트리를 사용한다. (각 노드는 리프이거나 두 서브 노드를 갖는 경우) 이 문제에서는 임의의 서브 트리의 개수를 갖는 허프만 트리를 사용한다. (N-ary tree)

파일의 내용에 총 Z개의 서로 다른 글자가 있는 경우에 리프 노드의 개수는 Z개이다. 루트에서 리프로 향하는 경로 상에 쓰여 있는 숫자가 그 글자를 어떻게 인코딩할 것인지를 나타낸다. 노드에 쓰여 있는 숫자는 0부터 N-1까지이다.

자주 사용하는 글자를 루트와 가까운 곳에 놓고, 잘 사용하지 않는 글자를 먼 곳에 놓으면, 압축 효율을 늘릴 수 있다. 즉, 한 파일을 압축하는데 있어서 최소 개수의 N-ary 심볼을 사용한 트리를 허프만 트리라고 한다.

이 문제에서, 사용할 허프만 트리는 각 노드가 내부 노드이거나, 글자를 인코딩하는 리프 노드이다. 아무 글자도 인코딩하지 않는 dangling leave는 존재하지 않는다.

아래 그림은 N=3인 경우의 허프만 트리 예시이다. 'a'와 'e'는 심볼 1개로 인코딩 되며, 덜 사용하지 글자인 's'와 'p'는 심볼 2개, 드물게 사용하는 글자인 'x','q','y'는 세 개로 인코딩한다.

디코딩을 해야 원래 파일로 복원할 수 있기 때문에, 한 데이터를 인코딩하는데 사용한 트리를 기억하는 것이 중요하다. 트리를 저장하는 방법에는 여러 가지가 있다. 이 문제에서는 모든 Z개의 문자가 사전순으로 하나씩 쓰여 있는 파일을 인코딩한 결과를 저장하는 방식으로 트리를 저장할 것이다.

N과 위에서 저장한 트리가 주어졌을 때, 각각의 글자가 어떤 심볼로 인코딩 되는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 아래와 같이 세 줄로 이루어져 있다.

  • 파일에 들어있는 서로 다른 글자의 개수 2 ≤ Z ≤ 20
  • 허프만 트리의 arity를 나타내는 2 ≤ N ≤ 10 (N진 트리로 생각하면 됩니다. N = 2인 경우엔 binary, 3인 경우엔 ternary)
  • 모든 글자가 사전 순으로 한 번씩 나타난 파일을 인코딩 한 결과. 길이는 200을 넘지 않으며, 항상 [0, (N-1)]에 들어있는 숫자로만 이루어져 있다.

Z=5, N=2인 경우에 010011101100은 여러 가지 정답이 나올 수 있다. 하지만, 이 문제에서는 답이 유일한 경우만 입력으로 주어진다.

출력

각각의 테스트 케이스에 대해서, Z줄을 출력해야 한다. 각 줄은 original->encoding 형식이고, original은 글자, encoding은 허프만 트리에 의해서 인코딩된 결과이다. 

예제 입력 1

3
3
2
10011
4
2
000111010
19
10
01234678950515253545556575859

예제 출력 1

0->10
1->0
2->11
0->00
1->011
2->1
3->010
0->0
1->1
2->2
3->3
4->4
5->6
6->7
7->8
8->9
9->50
10->51
11->52
12->53
13->54
14->55
15->56
16->57
17->58
18->59
W3sicHJvYmxlbV9pZCI6Ijc5MDQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1YzhcdWQ1MDRcdWI5Y2MgXHVkMmI4XHViOWFjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWIzNzBcdWM3NzRcdWQxMzBcdWI5N2MgXHVjNTU1XHVjZDk1XHVkNTU4XHViMjk0IFx1YmMyOVx1YmM5NSBcdWM5MTFcdWM1ZDBcdWMxMWMgXHVjMGMxXHViMzAwXHVjODAxXHVjNzNjXHViODVjIFx1YWMwNFx1YjJlOFx1ZDU1YyBcdWJjMjlcdWJjOTVcdWM3NDAgXHVkNWM4XHVkNTA0XHViOWNjIFx1ZDJiOFx1YjlhY1x1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWQ1YzhcdWQ1MDRcdWI5Y2MgXHVkMmI4XHViOWFjXHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU1OFx1YmE3NCBcdWQ1NWMgXHVkMzBjXHVjNzdjXHVjNzc0IFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyOTQgXHViMzcwXHVjNzc0XHVkMTMwXHViOTdjIFx1YzU1NVx1Y2Q5NVx1ZDU1OFx1YWNlMCBcdWM1NTVcdWNkOTUgXHVkNTc0XHVjODFjXHVkNTU4XHViMjk0IFx1Yzc5MVx1YzVjNVx1Yzc0NCBcdWMxOTBcdWMyN2RcdWFjOGMgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjljZVx1Yzc0MCBcdWM3NTFcdWM2YTlcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDAgXHViYzE0XHVjNzc0XHViMTA4XHViOWFjIFx1ZDVjOFx1ZDUwNFx1YjljYyBcdWQyYjhcdWI5YWNcdWI5N2MgXHVjMGFjXHVjNmE5XHVkNTVjXHViMmU0LiAoXHVhYzAxIFx1YjE3OFx1YjRkY1x1YjI5NCBcdWI5YWNcdWQ1MDRcdWM3NzRcdWFjNzBcdWIwOTggXHViNDUwIFx1YzExY1x1YmUwYyBcdWIxNzhcdWI0ZGNcdWI5N2MgXHVhYzE2XHViMjk0IFx1YWNiZFx1YzZiMCkgXHVjNzc0IFx1YmIzOFx1YzgxY1x1YzVkMFx1YzExY1x1YjI5NCBcdWM3ODRcdWM3NThcdWM3NTggXHVjMTFjXHViZTBjIFx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhYzE2XHViMjk0IFx1ZDVjOFx1ZDUwNFx1YjljYyBcdWQyYjhcdWI5YWNcdWI5N2MgXHVjMGFjXHVjNmE5XHVkNTVjXHViMmU0LiAoTi1hcnkgdHJlZSk8XC9wPlxyXG5cclxuPHA+XHVkMzBjXHVjNzdjXHVjNzU4IFx1YjBiNFx1YzZhOVx1YzVkMCBcdWNkMWQgWlx1YWMxY1x1Yzc1OCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YWUwMFx1Yzc5MFx1YWMwMCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNWQwIFx1YjlhY1x1ZDUwNCBcdWIxNzhcdWI0ZGNcdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0IFpcdWFjMWNcdWM3NzRcdWIyZTQuIFx1YjhlOFx1ZDJiOFx1YzVkMFx1YzExYyBcdWI5YWNcdWQ1MDRcdWI4NWMgXHVkNWE1XHVkNTU4XHViMjk0IFx1YWNiZFx1Yjg1YyBcdWMwYzFcdWM1ZDAgXHVjNGYwXHVjNWVjIFx1Yzc4OFx1YjI5NCBcdWMyMmJcdWM3OTBcdWFjMDAgXHVhZGY4IFx1YWUwMFx1Yzc5MFx1Yjk3YyBcdWM1YjRcdWI1YmJcdWFjOGMgXHVjNzc4XHVjZjU0XHViNTI5XHVkNTYwIFx1YWM4M1x1Yzc3OFx1YzljMFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuIFx1YjE3OFx1YjRkY1x1YzVkMCBcdWM0ZjBcdWM1ZWMgXHVjNzg4XHViMjk0IFx1YzIyYlx1Yzc5MFx1YjI5NCAwXHViZDgwXHVkMTMwIE4tMVx1YWU0Y1x1YzljMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzkwXHVjOGZjIFx1YzBhY1x1YzZhOVx1ZDU1OFx1YjI5NCBcdWFlMDBcdWM3OTBcdWI5N2MgXHViOGU4XHVkMmI4XHVjNjQwIFx1YWMwMFx1YWU0Y1x1YzZiNCBcdWFjZjNcdWM1ZDAgXHViMTkzXHVhY2UwLCBcdWM3OTggXHVjMGFjXHVjNmE5XHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NCBcdWFlMDBcdWM3OTBcdWI5N2MgXHViYTNjIFx1YWNmM1x1YzVkMCBcdWIxOTNcdWM3M2NcdWJhNzQsIFx1YzU1NVx1Y2Q5NSBcdWQ2YThcdWM3MjhcdWM3NDQgXHViMjk4XHViOWI0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzk4OSwgXHVkNTVjIFx1ZDMwY1x1Yzc3Y1x1Yzc0NCBcdWM1NTVcdWNkOTVcdWQ1NThcdWIyOTRcdWIzNzAgXHVjNzg4XHVjNWI0XHVjMTFjIFx1Y2Q1Y1x1YzE4YyBcdWFjMWNcdWMyMThcdWM3NTggTi1hcnkgXHVjMmVjXHViY2ZjXHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU1YyBcdWQyYjhcdWI5YWNcdWI5N2MgXHVkNWM4XHVkNTA0XHViOWNjIFx1ZDJiOFx1YjlhY1x1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWJiMzhcdWM4MWNcdWM1ZDBcdWMxMWMsIFx1YzBhY1x1YzZhOVx1ZDU2MCBcdWQ1YzhcdWQ1MDRcdWI5Y2MgXHVkMmI4XHViOWFjXHViMjk0IFx1YWMwMSBcdWIxNzhcdWI0ZGNcdWFjMDAgXHViMGI0XHViZDgwIFx1YjE3OFx1YjRkY1x1Yzc3NFx1YWM3MFx1YjA5OCwgXHVhZTAwXHVjNzkwXHViOTdjIFx1Yzc3OFx1Y2Y1NFx1YjUyOVx1ZDU1OFx1YjI5NCBcdWI5YWNcdWQ1MDQgXHViMTc4XHViNGRjXHVjNzc0XHViMmU0LiBcdWM1NDRcdWJiMzQgXHVhZTAwXHVjNzkwXHViM2M0IFx1Yzc3OFx1Y2Y1NFx1YjUyOVx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTQgZGFuZ2xpbmcgbGVhdmVcdWIyOTQgXHVjODc0XHVjN2FjXHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1Yzc0MCBOPTNcdWM3NzggXHVhY2JkXHVjNmIwXHVjNzU4IFx1ZDVjOFx1ZDUwNFx1YjljYyBcdWQyYjhcdWI5YWMgXHVjNjA4XHVjMmRjXHVjNzc0XHViMmU0LiAmIzM5O2EmIzM5O1x1YzY0MCAmIzM5O2UmIzM5O1x1YjI5NCBcdWMyZWNcdWJjZmMgMVx1YWMxY1x1Yjg1YyBcdWM3NzhcdWNmNTRcdWI1MjkgXHViNDE4XHViYTcwLCBcdWIzNWMgXHVjMGFjXHVjNmE5XHVkNTU4XHVjOWMwIFx1YWUwMFx1Yzc5MFx1Yzc3OCAmIzM5O3MmIzM5O1x1YzY0MCAmIzM5O3AmIzM5O1x1YjI5NCBcdWMyZWNcdWJjZmMgMlx1YWMxYywgXHViNGRjXHViYjNjXHVhYzhjIFx1YzBhY1x1YzZhOVx1ZDU1OFx1YjI5NCBcdWFlMDBcdWM3OTBcdWM3NzggJiMzOTt4JiMzOTssJiMzOTtxJiMzOTssJiMzOTt5JiMzOTtcdWIyOTQgXHVjMTM4IFx1YWMxY1x1Yjg1YyBcdWM3NzhcdWNmNTRcdWI1MjlcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvaG10cmVlLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjI4NnB4OyB3aWR0aDoyOTFweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWI1MTRcdWNmNTRcdWI1MjlcdWM3NDQgXHVkNTc0XHVjNTdjIFx1YzZkMFx1Yjc5OCBcdWQzMGNcdWM3N2NcdWI4NWMgXHViY2Y1XHVjNmQwXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWQ1NWMgXHViMzcwXHVjNzc0XHVkMTMwXHViOTdjIFx1Yzc3OFx1Y2Y1NFx1YjUyOVx1ZDU1OFx1YjI5NFx1YjM3MCBcdWMwYWNcdWM2YTlcdWQ1NWMgXHVkMmI4XHViOWFjXHViOTdjIFx1YWUzMFx1YzViNVx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzQgXHVjOTExXHVjNjk0XHVkNTU4XHViMmU0LiBcdWQyYjhcdWI5YWNcdWI5N2MgXHVjODAwXHVjN2E1XHVkNTU4XHViMjk0IFx1YmMyOVx1YmM5NVx1YzVkMFx1YjI5NCBcdWM1ZWNcdWI3ZWMgXHVhYzAwXHVjOWMwXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YmIzOFx1YzgxY1x1YzVkMFx1YzExY1x1YjI5NCBcdWJhYThcdWI0ZTAgWlx1YWMxY1x1Yzc1OCBcdWJiMzhcdWM3OTBcdWFjMDAgXHVjMGFjXHVjODA0XHVjMjFjXHVjNzNjXHViODVjIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM0ZjBcdWM1ZWMgXHVjNzg4XHViMjk0IFx1ZDMwY1x1Yzc3Y1x1Yzc0NCBcdWM3NzhcdWNmNTRcdWI1MjlcdWQ1NWMgXHVhY2IwXHVhY2ZjXHViOTdjIFx1YzgwMFx1YzdhNVx1ZDU1OFx1YjI5NCBcdWJjMjlcdWMyZGRcdWM3M2NcdWI4NWMgXHVkMmI4XHViOWFjXHViOTdjIFx1YzgwMFx1YzdhNVx1ZDU2MCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPk5cdWFjZmMgXHVjNzA0XHVjNWQwXHVjMTFjIFx1YzgwMFx1YzdhNVx1ZDU1YyBcdWQyYjhcdWI5YWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YWUwMFx1Yzc5MFx1YWMwMCBcdWM1YjRcdWI1YTQgXHVjMmVjXHViY2ZjXHViODVjIFx1Yzc3OFx1Y2Y1NFx1YjUyOSBcdWI0MThcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzc0IFx1YzEzOCBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWQzMGNcdWM3N2NcdWM1ZDAgXHViNGU0XHVjNWI0XHVjNzg4XHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVhZTAwXHVjNzkwXHVjNzU4IFx1YWMxY1x1YzIxOCAyICZsZTsgWiAmbGU7IDIwPFwvbGk+XHJcblx0PGxpPlx1ZDVjOFx1ZDUwNFx1YjljYyBcdWQyYjhcdWI5YWNcdWM3NTggYXJpdHlcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IDIgJmxlOyBOICZsZTsgMTAgKE5cdWM5YzQgXHVkMmI4XHViOWFjXHViODVjIFx1YzBkZFx1YWMwMVx1ZDU1OFx1YmE3NCBcdWI0MjlcdWIyYzhcdWIyZTQuIE4gPSAyXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkNCBiaW5hcnksIDNcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQ0IHRlcm5hcnkpPFwvbGk+XHJcblx0PGxpPlx1YmFhOFx1YjRlMCBcdWFlMDBcdWM3OTBcdWFjMDAgXHVjMGFjXHVjODA0IFx1YzIxY1x1YzczY1x1Yjg1YyBcdWQ1NWMgXHViYzg4XHVjNTI5IFx1YjA5OFx1ZDBjMFx1YjA5YyBcdWQzMGNcdWM3N2NcdWM3NDQgXHVjNzc4XHVjZjU0XHViNTI5IFx1ZDU1YyBcdWFjYjBcdWFjZmMuIFx1YWUzOFx1Yzc3NFx1YjI5NCAyMDBcdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YzczY1x1YmE3MCwgXHVkNTZkXHVjMGMxIFswLCAoTi0xKV1cdWM1ZDAgXHViNGU0XHVjNWI0XHVjNzg4XHViMjk0IFx1YzIyYlx1Yzc5MFx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlo9NSwgTj0yXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMCAwMTAwMTExMDExMDBcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMCBcdWM4MTVcdWIyZjVcdWM3NzQgXHViMDk4XHVjNjJjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHVjNzc0IFx1YmIzOFx1YzgxY1x1YzVkMFx1YzExY1x1YjI5NCBcdWIyZjVcdWM3NzQgXHVjNzIwXHVjNzdjXHVkNTVjIFx1YWNiZFx1YzZiMFx1YjljYyBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgWlx1YzkwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWFjMDEgXHVjOTA0XHVjNzQwIG9yaWdpbmFsLSZndDtlbmNvZGluZyBcdWQ2MTVcdWMyZGRcdWM3NzRcdWFjZTAsIG9yaWdpbmFsXHVjNzQwIFx1YWUwMFx1Yzc5MCwgZW5jb2RpbmdcdWM3NDAgXHVkNWM4XHVkNTA0XHViOWNjIFx1ZDJiOFx1YjlhY1x1YzVkMCBcdWM3NThcdWQ1NzRcdWMxMWMgXHVjNzc4XHVjZjU0XHViNTI5XHViNDFjIFx1YWNiMFx1YWNmY1x1Yzc3NFx1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI3OTA0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiSHVmZm1hbiBUcmVlcyIsImRlc2NyaXB0aW9uIjoiPHA+QSByZWxhdGl2ZWx5IHNpbXBsZSBtZXRob2QgZm9yIGNvbXByZXNzaW5nIGRhdGEgd29ya3MgYnkgY3JlYXRpbmcgYSBzby1jYWxsZWQgSHVmZm1hbiB0cmVlIGZvciBhIFx1ZmIwMWxlIGFuZCB1c2luZyBpdCB0byBjb21wcmVzcyBhbmQgZGVjb21wcmVzcyB0aGUgZGF0YSBpdCBjb250YWlucy4gRm9yIG1vc3QgYXBwbGljYXRpb25zLCBiaW5hcnkgSHVmZm1hbiB0cmVlcyBhcmUgdXNlZCAoaS5lLiwgZWFjaCBub2RlIGlzIGVpdGhlciBhIGxlYWYgb3IgaGFzIGV4YWN0bHkgdHdvIHN1Yi1ub2RlcykuIE9uZSBjYW4sIGhvd2V2ZXIsIGNvbnN0cnVjdCBIdWZmbWFuIHRyZWVzIHdpdGggYW4gYXJiaXRyYXJ5IG51bWJlciBvZiBzdWItdHJlZXMgKGkuZSwgdGVybmFyeSBvciwgaW4gZ2VuZXJhbCwgTi1hcnkgdHJlZXMpLjxcL3A+XHJcblxyXG48cD5BIEh1ZmZtYW4gdHJlZSBmb3IgYSBcdWZiMDFsZSBjb250YWluaW5nIFogZGlmZmVyZW50IGNoYXJhY3RlcnMgaGFzIFogbGVhdmVzLiBUaGUgcGF0aCBmcm9tIHRoZSByb290IHRvIGEgbGVhZiB0aGF0IHJlcHJlc2VudHMgYSBjZXJ0YWluIGNoYXJhY3RlciBkZXRlcm1pbmVzIGl0cyBlbmNvZGluZzsgZWFjaCBzdGVwIHRvd2FyZHMgdGhlIGxlYWYgZGV0ZXJtaW5lcyBhbiBlbmNvZGluZyBjaGFyYWN0ZXIgKHdoaWNoIGNhbiBiZSAwLCAxLCAuLi4sIChOIDEpKS4gQnkgcGxhY2luZyBvZnRlbi1vY2N1cnJpbmcgY2hhcmFjdGVycyBjbG9zZXIgdG8gdGhlIHJvb3QsIGFuZCBsZXNzIG9mdGVuIG9jY3VycmluZyBjaGFyYWN0ZXJzIGZ1cnRoZXIgYXdheSBmcm9tIHRoZSByb290LCB0aGUgZGVzaXJhYmxlIGNvbXByZXNzaW9uIGlzIGFjaGlldmVkLiBTdHJpY3RseSBzcGVha2luZywgc3VjaCBhIHRyZWUgaXMgYSBIdWZmbWFuIHRyZWUgb25seSBpZiB0aGUgcmVzdWx0aW5nIGVuY29kaW5nIHRha2VzIHRoZSBtaW5pbWFsIG51bWJlciBvZk4tYXJ5IHN5bWJvbHMgdG8gZW5jb2RlIHRoZSBjb21wbGV0ZSBcdWZiMDFsZS48XC9wPlxyXG5cclxuPHA+Rm9yIHRoaXMgcHJvYmxlbSwgd2Ugb25seSBjb25zaWRlciB0cmVlcyB3aGVyZSBlYWNoIG5vZGUgaXMgZWl0aGVyIGFuIGludGVybmFsIG5vZGUsIG9yIGEgbGVhZiBlbmNvZGluZyBhIGNoYXJhY3RlcjsgdGhlcmUgYXJlIG5vIGRhbmdsaW5nIGxlYXZlc3RoYXQgZG8gbm90IGVuY29kZSBmb3IgYSBjaGFyYWN0ZXIuPFwvcD5cclxuXHJcbjxwPlRoZSBcdWZiMDFndXJlIGJlbG93IHNob3dzIGEgc2FtcGxlIHRlcm5hcnkgSHVmZm1hbiB0cmVlOyB0aGUgY2hhcmFjdGVycyAmcnNxdW87YSZyc3F1bzsgYW5kICZyc3F1bztlJnJzcXVvOyBhcmUgZW5jb2RlZCB1c2luZyBvbmUgdGVybmFyeSBzeW1ib2w7IHRoZSBsZXNzIGZyZXF1ZW50bHkgb2NjdXJyaW5nIGNoYXJhY3RlcnMgJnJzcXVvO3MmcnNxdW87IGFuZCAmcnNxdW87cCZyc3F1bzsgYXJlIGVuY29kZWQgdXNpbmcgdHdvIHRlcm5hcnkgc3ltYm9sczsgYW5kIHRoZSB2ZXJ5IHJhcmUgc3ltYm9scyAmcnNxdW87eCZyc3F1bzssICZyc3F1bztxJnJzcXVvOyBhbmQgJnJzcXVvO3kmcnNxdW87IGFyZSBlbmNvZGVkIHVzaW5nIHRocmVlIHRlcm5hcnkgc3ltYm9scyBlYWNoLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2htdHJlZS5wbmdcIiBzdHlsZT1cImhlaWdodDoyODZweDsgd2lkdGg6MjkxcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+T2YgY291cnNlLCBpZiB3ZSB3YW50IHRvIGRlY29tcHJlc3MgYSBsaXN0IG9mIE4tYXJ5IHN5bWJvbHMgbGF0ZXIgb24sIGl0IGlzIGltcG9ydGFudCB0byBrbm93IHdoaWNoIHRyZWUgd2FzIHVzZWQgdG8gY29tcHJlc3MgdGhlIGRhdGEuIFRoaXMgY2FuIGJlIGRvbmUgaW4gc2V2ZXJhbCB3YXlzLiBJbiB0aGlzIHByb2JsZW0gd2UgdXNlIHRoZSBmb2xsb3dpbmcgbWV0aG9kOiB0aGUgc3RyZWFtIG9mIGRhdGEgd2lsbCBiZSBwcmVjZWRlZCBieSBhIGhlYWRlciBjb25zaXN0aW5nIG9mIHRoZSBlbmNvZGVkIHZlcnNpb25zIG9mIHRoZSBaIGNoYXJhY3RlcnMgb2NjdXJyaW5nIGluIHRoZSBvcmlnaW5hbCBcdWZiMDFsZSwgaW4gbGV4aWNvZ3JhcGhpY2FsIG9yZGVyLjxcL3A+XHJcblxyXG48cD5HaXZlbiB0aGUgbnVtYmVyIG9mIHNvdXJjZSBzeW1ib2xzIFosIGEgdmFsdWUgTiBkZW5vdGluZyB0aGUgJnJzcXVvO2FyaXR5JnJzcXVvOyBvZiB0aGUgSHVmZm1hbiB0cmVlLCBhbmQgYSBoZWFkZXIsIGdpdmUgdGhlIG1hcHBpbmcgZnJvbSBzb3VyY2Ugc3ltYm9scyB0byBlbmNvZGVkIHN5bWJvbHMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgc3RhcnRzIHdpdGggYSBzaW5nbGUgaW50ZWdlciBUIG9uIGEgc2VwYXJhdGUgbGluZSwgZGVub3RpbmcgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIHRoYXQmbmJzcDtmb2xsb3cuIE5leHQsIGZvciBlYWNoIG9mIHRoZSBUIHRlc3QgY2FzZXMsIHRocmVlIGxpbmVzIGZvbGxvdzo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5UaGUgbnVtYmVyIG9mIGRpZmZlcmVudCBjaGFyYWN0ZXJzIGluIHRoZSBcdWZiMDFsZSAoMiAmbGU7IFogJmxlOyAyMCk7PFwvbGk+XHJcblx0PGxpPlRoZSBudW1iZXIgTiwgZGVub3RpbmcgdGhlICZyc3F1bzthcml0eSZyc3F1bzsgb2YgdGhlIEh1ZmZtYW4gdHJlZSAoMiAmbGU7IE4gJmxlOyAxMCk7PFwvbGk+XHJcblx0PGxpPkEgc3RyaW5nIHJlcHJlc2VudGluZyB0aGUgaGVhZGVyIG9mIHRoZSByZWNlaXZlZCBtZXNzYWdlOyBlYWNoIGNoYXJhY3RlciB3aWxsIGJlIGEgZGlnaXQgaW4gdGhlIHJhbmdlIFswLCBOLTFdLiBUaGlzIHN0cmluZyB3aWxsIGNvbnRhaW4gbGVzcyB0aGFuIDIwMCBjaGFyYWN0ZXJzLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPk5vdGU6IEFsdGhvdWdoIHJhcmUsIGl0IGlzIHBvc3NpYmxlIGZvciBhIGhlYWRlciB0byBoYXZlIG11bHRpcGxlIGludGVycHJldGF0aW9ucyAoZS5nLiwgdGhlIGhlYWRlciAmcnNxdW87MDEwMDExMTAxMTAwJnJzcXVvOyB3aXRoIFogPSA1IGFuZCBOID0gMikuIEl0IGlzIGd1YXJhbnRlZWQgdGhhdCBhbGwgY2FzZXMgaW4gdGhlIHRlc3QgaW5wdXQgaGF2ZSBhIHVuaXF1ZSBzb2x1dGlvbi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBvZiB0aGUgVCB0ZXN0LWNhc2VzLCBwcmludCBaIGxpbmVzIGdpdmluZyB0aGUgZW5jb2RlZCB2ZXJzaW9uIG9mIGVhY2ggb2YgdGhlIFogY2hhcmFjdGVycyBpbiB0aGUgdGVzdGNhc2UgaW4gYXNjZW5kaW5nIG9yZGVyLiBVc2UgdGhlIGZvcm1hdCBvcmlnaW5hbC0mZ3Q7ZW5jb2RpbmcsIHdoZXJlIG9yaWdpbmFsIGlzIGEgZGVjaW1hbCB2YWx1ZSBpbiB0aGUgcmFuZ2UgWzAsIChaIC0gMSldLCBhbmQgZW5jb2RpbmcgaXMgdGhlIHN0cmluZyBvZiBlbmNvZGluZyBkaWdpdHMgZm9yIHRoaXMgc3ltYm9sIChlYWNoIGRpZ2l0IGlzICZnZTsgMCBhbmQgJmx0OyBOKS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2002 G번