시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 256 MB100403150.820%

문제

과학에서 단위는 어디에서나 존재한다. 물리에서 단위는 거리(미터, 키로미터 등), 무게(키로그램, 그램 등), 그리고 다른 많은 양을 측정하는데 사용한다. 컴퓨터 과학자들은 용량의 단위(키로바이트, 메가바이트, ...)를 만들어 사용하고 있다. 당신은 여러 단위들이 주어질 때 그들이 몇 배 차이나는지를 찾는 프로그램을 작성하고자 한다.

여러 단위간의 관계를 표현하는 방법은 여러 가지가 존재하지만, 의미하는 바는 같다. 예를 들자면 미터계에 존재하는 단위는 1km = 1000m, 1m = 100cm, 1cm = 10mm로 표현할 수 있다. 다른 방법으로는 1km = 100000cm, 1km = 1000000mm, 1m = 1000mm 가 있다. 두 표현법에서는 모두 1km = 1000m = 100000cm = 1000000mm라는 똑같은 관계를 유추할 수 있다.

이 문제에서 당신은 단위를 큰 순서에서 작은 순서대로 정렬하고 싶다. 예제로 cm, km, m, mm중에서 km이 가장 큰 단위이며 그 이유는 1km이 1cm, 1m, 1mm보다 크기 때문이다. 남은 단위들도 같은 방법으로 정렬할 수 있다. 이 예제에 대한 답은 km m cm mm이다.

이 문제에서 단위간 크기 차이는 정수배로만 나게 된다. 그렇기 때문에 1인치 = 2.54cm같은 단위는 고려하지 않아도 된다. 또한 언제나 큰 단위가 작은 단위의 몇 배로 표현되도록 입력이 주어진다.

입력

여러 개의 테스트 케이스가 주어진다. 각 테스트 케이스는 단위의 가짓수 N(2 ≤ N ≤ 10)으로 시작한다. 이어지는 줄에는 N개의 단위들이 주어진다. 각 단위는 최대 5글자이며 대소문자를 구분한다. 이어지는 N - 1개의 줄에는 서로 다른 두 단위의 관계가 주어진다. 입력 형식은 "단위의 이름" "=" "1보다 큰 정수" "왼쪽 단위보다 작은 오른쪽 단위의 이름" 순이다. 각 줄은 오른쪽의 작은 단위와 왼쪽 큰 단위가 몇 배 차이가 나는지를 설명한다. 각 단위는 N - 1줄중에 한번 이상 등장하며 주어진 입력만으로 전 단위간의 관계가 파악 가능하도록 주어진다. 단위간의 관계는 (231 - 1) 배보다 같거나 작은 차이가 나도록 구성되어 있다.

모든 입력이 끝나면 0이 주어진다.

출력

각 테스트 케이스에 대해서 한 줄에 걸쳐 단위들의 관계를 출력한다. 단위들은 왼쪽에서 오른쪽으로, 높은 단위에서 낮은 단위로 정렬되어 있어야 하며 가장 왼쪽의 단위가 1일 때 나머지 단위들은 몇인지를 "=" 기호를 통해서 나열한다.

예제 입력 1

4
km m mm cm
km = 1000 m
m = 100 cm
cm = 10 mm
4
m mm cm km
km = 100000 cm
km = 1000000 mm
m = 1000 mm
6
MiB Mib KiB Kib B b
B = 8 b
MiB = 1024 KiB
KiB = 1024 B
Mib = 1048576 b
Mib = 1024 Kib
6
Kib B MiB Mib KiB b
B = 8 b
MiB = 1048576 B
MiB = 1024 KiB
MiB = 8192 Kib
MiB = 8 Mib
0

예제 출력 1

1km = 1000m = 100000cm = 1000000mm
1km = 1000m = 100000cm = 1000000mm
1MiB = 8Mib = 1024KiB = 8192Kib = 1048576B = 8388608b
1MiB = 8Mib = 1024KiB = 8192Kib = 1048576B = 8388608b
W3sicHJvYmxlbV9pZCI6IjEwNDc4IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViMmU4XHVjNzA0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWFjZmNcdWQ1NTlcdWM1ZDBcdWMxMWMgXHViMmU4XHVjNzA0XHViMjk0IFx1YzViNFx1YjUxNFx1YzVkMFx1YzExY1x1YjA5OCBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTQuIFx1YmIzY1x1YjlhY1x1YzVkMFx1YzExYyBcdWIyZThcdWM3MDRcdWIyOTQgXHVhYzcwXHViOWFjKFx1YmJmOFx1ZDEzMCwgXHVkMGE0XHViODVjXHViYmY4XHVkMTMwIFx1YjRmMSksIFx1YmIzNFx1YWM4YyhcdWQwYTRcdWI4NWNcdWFkZjhcdWI3YTgsIFx1YWRmOFx1YjdhOCBcdWI0ZjEpLCBcdWFkZjhcdWI5YWNcdWFjZTAgXHViMmU0XHViOTc4IFx1YjljZVx1Yzc0MCBcdWM1OTFcdWM3NDQgXHVjZTIxXHVjODE1XHVkNTU4XHViMjk0XHViMzcwIFx1YzBhY1x1YzZhOVx1ZDU1Y1x1YjJlNC4gXHVjZWY0XHVkNGU4XHVkMTMwIFx1YWNmY1x1ZDU1OVx1Yzc5MFx1YjRlNFx1Yzc0MCBcdWM2YTlcdWI3YzlcdWM3NTggXHViMmU4XHVjNzA0KFx1ZDBhNFx1Yjg1Y1x1YmMxNFx1Yzc3NFx1ZDJiOCwgXHViYTU0XHVhYzAwXHViYzE0XHVjNzc0XHVkMmI4LCAuLi4pXHViOTdjIFx1YjljY1x1YjRlNFx1YzViNCBcdWMwYWNcdWM2YTlcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWIyZjlcdWMyZTBcdWM3NDAgXHVjNWVjXHViN2VjIFx1YjJlOFx1YzcwNFx1YjRlNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzggXHViNTRjIFx1YWRmOFx1YjRlNFx1Yzc3NCBcdWJhODcgXHViYzMwIFx1Y2MyOFx1Yzc3NFx1YjA5OFx1YjI5NFx1YzljMFx1Yjk3YyBcdWNjM2VcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YWNlMFx1Yzc5MCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzVlY1x1YjdlYyBcdWIyZThcdWM3MDRcdWFjMDRcdWM3NTggXHVhZDAwXHVhY2M0XHViOTdjIFx1ZDQ1Y1x1ZDYwNFx1ZDU1OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMFx1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1Yzc1OFx1YmJmOFx1ZDU1OFx1YjI5NCBcdWJjMTRcdWIyOTQgXHVhYzE5XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNzkwXHViYTc0IFx1YmJmOFx1ZDEzMFx1YWNjNFx1YzVkMCBcdWM4NzRcdWM3YWNcdWQ1NThcdWIyOTQgXHViMmU4XHVjNzA0XHViMjk0IDFrbSA9IDEwMDBtLCAxbSA9IDEwMGNtLCAxY20gPSAxMG1tXHViODVjIFx1ZDQ1Y1x1ZDYwNFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWIyZTRcdWI5NzggXHViYzI5XHViYzk1XHVjNzNjXHViODVjXHViMjk0IDFrbSA9IDEwMDAwMGNtLCAxa20gPSAxMDAwMDAwbW0sIDFtID0gMTAwMG1tIFx1YWMwMCBcdWM3ODhcdWIyZTQuIFx1YjQ1MCBcdWQ0NWNcdWQ2MDRcdWJjOTVcdWM1ZDBcdWMxMWNcdWIyOTQgXHViYWE4XHViNDUwIDFrbSA9IDEwMDBtID0gMTAwMDAwY20gPSAxMDAwMDAwbW1cdWI3N2NcdWIyOTQgXHViNjExXHVhYzE5XHVjNzQwIFx1YWQwMFx1YWNjNFx1Yjk3YyBcdWM3MjBcdWNkOTRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0IFx1YmIzOFx1YzgxY1x1YzVkMFx1YzExYyBcdWIyZjlcdWMyZTBcdWM3NDAgXHViMmU4XHVjNzA0XHViOTdjIFx1ZDA3MCBcdWMyMWNcdWMxMWNcdWM1ZDBcdWMxMWMgXHVjNzkxXHVjNzQwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4MTVcdWI4MmNcdWQ1NThcdWFjZTAgXHVjMmY2XHViMmU0LiBcdWM2MDhcdWM4MWNcdWI4NWMgY20sIGttLCBtLCBtbVx1YzkxMVx1YzVkMFx1YzExYyBrbVx1Yzc3NCBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YjJlOFx1YzcwNFx1Yzc3NFx1YmE3MCBcdWFkZjggXHVjNzc0XHVjNzIwXHViMjk0IDFrbVx1Yzc3NCAxY20sIDFtLCAxbW1cdWJjZjRcdWIyZTQgXHVkMDZjXHVhZTMwIFx1YjU0Y1x1YmIzOFx1Yzc3NFx1YjJlNC4gXHViMGE4XHVjNzQwIFx1YjJlOFx1YzcwNFx1YjRlNFx1YjNjNCBcdWFjMTlcdWM3NDAgXHViYzI5XHViYzk1XHVjNzNjXHViODVjIFx1YzgxNVx1YjgyY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVjNjA4XHVjODFjXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWIyZjVcdWM3NDAga20gbSBjbSBtbVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0IFx1YmIzOFx1YzgxY1x1YzVkMFx1YzExYyBcdWIyZThcdWM3MDRcdWFjMDQgXHVkMDZjXHVhZTMwIFx1Y2MyOFx1Yzc3NFx1YjI5NCBcdWM4MTVcdWMyMThcdWJjMzBcdWI4NWNcdWI5Y2MgXHViMDk4XHVhYzhjIFx1YjQxY1x1YjJlNC4gXHVhZGY4XHViODA3XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCAxXHVjNzc4XHVjZTU4ID0gMi41NGNtXHVhYzE5XHVjNzQwIFx1YjJlOFx1YzcwNFx1YjI5NCBcdWFjZTBcdWI4MjRcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNTQ0XHViM2M0IFx1YjQxY1x1YjJlNC4gXHViNjEwXHVkNTVjIFx1YzViOFx1YzgxY1x1YjA5OCBcdWQwNzAgXHViMmU4XHVjNzA0XHVhYzAwIFx1Yzc5MVx1Yzc0MCBcdWIyZThcdWM3MDRcdWM3NTggXHViYTg3IFx1YmMzMFx1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWI0MThcdWIzYzRcdWI4NWQgXHVjNzg1XHViODI1XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YjJlOFx1YzcwNFx1Yzc1OCBcdWFjMDBcdWM5ZDNcdWMyMTggTigyICZsZTsgTiAmbGU7IDEwKVx1YzczY1x1Yjg1YyBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YzViNFx1YzljMFx1YjI5NCBcdWM5MDRcdWM1ZDBcdWIyOTQgTlx1YWMxY1x1Yzc1OCBcdWIyZThcdWM3MDRcdWI0ZTRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHViMmU4XHVjNzA0XHViMjk0IFx1Y2Q1Y1x1YjMwMCA1XHVhZTAwXHVjNzkwXHVjNzc0XHViYTcwIFx1YjMwMFx1YzE4Y1x1YmIzOFx1Yzc5MFx1Yjk3YyBcdWFkNmNcdWJkODRcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YzViNFx1YzljMFx1YjI5NCBOIC0gMVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWI0NTAgXHViMmU4XHVjNzA0XHVjNzU4IFx1YWQwMFx1YWNjNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc4NVx1YjgyNSBcdWQ2MTVcdWMyZGRcdWM3NDAgJnF1b3Q7XHViMmU4XHVjNzA0XHVjNzU4IFx1Yzc3NFx1Yjk4NCZxdW90OyAmcXVvdDs9JnF1b3Q7ICZxdW90OzFcdWJjZjRcdWIyZTQgXHVkMDcwIFx1YzgxNVx1YzIxOCZxdW90OyAmcXVvdDtcdWM2N2NcdWNhYmQgXHViMmU4XHVjNzA0XHViY2Y0XHViMmU0IFx1Yzc5MVx1Yzc0MCBcdWM2MjRcdWI5NzhcdWNhYmQgXHViMmU4XHVjNzA0XHVjNzU4IFx1Yzc3NFx1Yjk4NCZxdW90OyBcdWMyMWNcdWM3NzRcdWIyZTQuIFx1YWMwMSBcdWM5MDRcdWM3NDAgXHVjNjI0XHViOTc4XHVjYWJkXHVjNzU4IFx1Yzc5MVx1Yzc0MCBcdWIyZThcdWM3MDRcdWM2NDAgXHVjNjdjXHVjYWJkIFx1ZDA3MCBcdWIyZThcdWM3MDRcdWFjMDAgXHViYTg3IFx1YmMzMCBcdWNjMjhcdWM3NzRcdWFjMDAgXHViMDk4XHViMjk0XHVjOWMwXHViOTdjIFx1YzEyNFx1YmE4NVx1ZDU1Y1x1YjJlNC4gXHVhYzAxIFx1YjJlOFx1YzcwNFx1YjI5NCBOIC0gMVx1YzkwNFx1YzkxMVx1YzVkMCBcdWQ1NWNcdWJjODggXHVjNzc0XHVjMGMxIFx1YjRmMVx1YzdhNVx1ZDU1OFx1YmE3MCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjNzg1XHViODI1XHViOWNjXHVjNzNjXHViODVjIFx1YzgwNCBcdWIyZThcdWM3MDRcdWFjMDRcdWM3NTggXHVhZDAwXHVhY2M0XHVhYzAwIFx1ZDMwY1x1YzU0NSBcdWFjMDBcdWIyYTVcdWQ1NThcdWIzYzRcdWI4NWQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZThcdWM3MDRcdWFjMDRcdWM3NTggXHVhZDAwXHVhY2M0XHViMjk0ICgyPHN1cD4zMTxcL3N1cD4gLSAxKSBcdWJjMzBcdWJjZjRcdWIyZTQgXHVhYzE5XHVhYzcwXHViMDk4IFx1Yzc5MVx1Yzc0MCBcdWNjMjhcdWM3NzRcdWFjMDAgXHViMDk4XHViM2M0XHViODVkIFx1YWQ2Y1x1YzEzMVx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCBcdWM3ODVcdWI4MjVcdWM3NzQgXHViMDVkXHViMDk4XHViYTc0IDBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMCBcdWIyZThcdWM3MDRcdWI0ZTRcdWM3NTggXHVhZDAwXHVhY2M0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViMmU4XHVjNzA0XHViNGU0XHVjNzQwIFx1YzY3Y1x1Y2FiZFx1YzVkMFx1YzExYyBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3M2NcdWI4NWMsIFx1YjE5Mlx1Yzc0MCBcdWIyZThcdWM3MDRcdWM1ZDBcdWMxMWMgXHViMGFlXHVjNzQwIFx1YjJlOFx1YzcwNFx1Yjg1YyBcdWM4MTVcdWI4MmNcdWI0MThcdWM1YjQgXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1OFx1YmE3MCBcdWFjMDBcdWM3YTUgXHVjNjdjXHVjYWJkXHVjNzU4IFx1YjJlOFx1YzcwNFx1YWMwMCAxXHVjNzdjIFx1YjU0YyBcdWIwOThcdWJhMzhcdWM5YzAgXHViMmU4XHVjNzA0XHViNGU0XHVjNzQwIFx1YmE4N1x1Yzc3OFx1YzljMFx1Yjk3YyAmcXVvdDs9JnF1b3Q7IFx1YWUzMFx1ZDYzOFx1Yjk3YyBcdWQxYjVcdWQ1NzRcdWMxMWMgXHViMDk4XHVjNWY0XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjEwNDc4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVW5pdHMiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSB1c2Ugb2YgdW5pdHMgaXMgdWJpcXVpdG91cyBpbiBzY2llbmNlLiBQaHlzaWNzIHVzZXMgdW5pdHMgdG8gZGlzdGluZ3Vpc2ggZGlzdGFuY2UgKGUuZy4sIG1ldGVycywga2lsb21ldGVycyksIHdlaWdodCAoZS5nLiwga2lsb2dyYW1zLCBncmFtcyksIGFuZCBtYW55IG90aGVyIHF1YW50aXRpZXMuIENvbXB1dGVyIHNjaWVudGlzdHMgaGF2ZSBzcGVjaWFsaXplZCB1bml0cyB0byBkZXNjcmliZSBzdG9yYWdlIGNhcGFjaXR5IChlLmcuLCBraWJpYnl0ZXMsIG1lYmlieXRlcywgZXRjLikuIFlvdSBhcmUgdG8gd3JpdGUgYSBwcm9ncmFtIHRvIGRpc3BsYXkgdGhlIGNvbnZlcnNpb24gZmFjdG9ycyBmb3IgYSBzZXQgb2YgdW5pdHMuPFwvcD5cclxuXHJcbjxwPlNwZWNpZnlpbmcgdGhlIHJlbGF0aW9uc2hpcCBiZXR3ZWVuIHZhcmlvdXMgdW5pdHMgY2FuIGJlIGRvbmUgaW4gbWFueSBkaWZmZXJlbnQsIGJ1dCBlcXVpdmFsZW50LCB3YXlzLiBGb3IgZXhhbXBsZSwgdGhlIHVuaXRzIGZvciBtZXRyaWMgZGlzdGFuY2UgY2FuIGJlIHNwZWNpZmllZCBhcyB0aGUgZ3JvdXAgb2YgcmVsYXRpb25zaGlwcyBiZXR3ZWVuIHBhaXJzIGZvciB1bml0czogMWttPTEwMDBtLCAxbT0xMDBjbSwgYW5kIDFjbT0xMG1tLiBBbiBhbHRlcm5hdGl2ZSBzZXQgb2YgcGFpcnMgY29uc2lzdHMgb2Y6IDFrbT0xMDAwMDBjbSwgMWttPTEwMDAwMDBtbSwgYW5kIDFtPTEwMDBtbS4gSW4gZWl0aGVyIHByZXNlbnRhdGlvbiwgdGhlIHNhbWUgcmVsYXRpb25zaGlwIGNhbiBiZSBpbmZlcnJlZDogMWttPTEwMDBtPTEwMDAwMGNtPTEwMDAwMDBtbS48XC9wPlxyXG5cclxuPHA+Rm9yIHRoaXMgcHJvYmxlbSwgdGhlIHVuaXRzIGFyZSB0byBiZSBzb3J0ZWQgYWNjb3JkaW5nIHRvIHRoZWlyIGRlc2NlbmRpbmcgc2l6ZS4gRm9yIGV4YW1wbGUsIGFtb25nIHRoZSBsZW5ndGggdW5pdHMgY20sIGttLCBtLCBtbSwga20gaXMgY29uc2lkZXJlZCB0aGUgYmlnZ2VzdCB1bml0IHNpbmNlIDFrbSBjb3JyZXNwb25kcyB0byBhIGxlbmd0aCBncmVhdGVyIHRoYW4gMWNtLCAxbSwgYW5kIDFtbS4gVGhlIHJlbWFpbmluZyB1bml0cyBjYW4gYmUgc29ydGVkIHNpbWlsYXJseS4gRm9yIHRoaXMgc2V0LCB0aGUgc29ydGVkIG9yZGVyIHdvdWxkIGJlOiBrbSwgbSwgY20sIG1tLjxcL3A+XHJcblxyXG48cD5UaGlzIHByb2JsZW0gaXMgbGltaXRlZCB0byB1bml0LXN5c3RlbXMgd2hvc2UgY29udmVyc2lvbiBmYWN0b3JzIGFyZSBpbnRlZ2VyIG11bHRpcGxlcy4gVGh1cywgZmFjdG9ycyBzdWNoIGFzIDEgaW5jaCA9IDIuNTQgY20gd2lsbCBub3QgYmUgY29uc2lkZXJlZC4gRnVydGhlciwgdGhlIHNldCBvZiB1bml0cyBhbmQgdGhlIHByb3ZpZGUgY29udmVyc2lvbnMgd2lsbCBhbHdheXMgcGVybWl0IGEgbGFyZ2VyIHVuaXQgdG8gYmUgZXhwcmVzc2VkIGFzIGFuIGludGVnZXIgbXVsdGlwbGUgb2YgdGhlIG5leHQgc21hbGxlciB1bml0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IHdpbGwgY29uc2lzdCBvZiBzZXZlcmFsIHByb2JsZW1zLiBFYWNoIHByb2JsZW0gYmVnaW5zIHdpdGggYSBsaW5lIGdpdmluZyB0aGUgbnVtYmVyIG9mIHVuaXRzLCBOLCB3aGVyZSBOIGlzIGFuIGludGVnZXIgaW4gdGhlIGludGVydmFsIFsyLCAxMF0uIFRoZSBmb2xsb3dpbmcgbGluZSB3aWxsIGNvbnRhaW4gTiB1bmlxdWUgY2FzZS1zZW5zaXRpdmUgdW5pdHMsIGVhY2ggb2Ygd2hpY2ggY29uc2lzdHMgb2YgYXQgbW9zdCA1IGNoYXJhY3RlcnMuIEZvbGxvd2luZyB0aGUgc2V0IG9mIHVuaXRzIHdpbGwgYmUgTi0xIHVuaXF1ZSBsaW5lcywgZWFjaCBzcGVjaWZ5aW5nIGEgcmVsYXRpb25zaGlwIGJldHdlZW4gdHdvIGRpZmZlcmVudCB1bml0cywgd2l0aCB0aGUgZm9ybWF0IGNvbnRhaW5pbmcgdGhlIGZvbGxvd2luZyBmb3VyIHNwYWNlLXNlcGFyYXRlZCBwaWVjZXM6IG5hbWUgb2YgdGhlIHVuaXQ7IGFuICZxdW90Oz0mcXVvdDs7IGEgcG9zaXRpdmUgaW50ZWdlciBtdWx0aXBsaWVyIGxhcmdlciB0aGFuIDE7IGFuZCB0aGUgbmFtZSBvZiBhIHNlY29uZCB1bml0IHRoYXQgaXMgc21hbGxlciB0aGFuIHRoZSBvbmUgdG8gdGhlIGxlZnQgb2YgdGhlIGVxdWFsIHNpZ24uIEVhY2ggb2YgdGhlc2UgbGluZXMgZXN0YWJsaXNoZXMgaG93IG1hbnkgdW5pdHMgYXJlIGVxdWl2YWxlbnQgdG8gdGhlIGxhcmdlciB1bml0IG9uIHRoZSBsZWZ0LiBFYWNoIHVuaXQgd2lsbCBhcHBlYXIgaW4gdGhlIHNldCBvZiBOLTEgbGluZXMgYW5kIHdpbGwgZ2l2ZW4gaW4gc3VjaCBhIHdheSB0byBlbnN1cmUgdGhlIGVudGlyZSBzeXN0ZW0gaXMgZGVmaW5lZC4gVGhlIHNldCBvZiBtdWx0aXBsZXMgd2lsbCB5aWVsZCBjb252ZXJzaW9uIGZhY3RvcnMgdGhhdCB3aWxsIG5vdCBleGNlZWQgMjxzdXA+MzE8XC9zdXA+ICZtaW51czsgMS48XC9wPlxyXG5cclxuPHA+QSBsaW5lIGNvbnRhaW5pbmcganVzdCBhIHplcm8gd2lsbCBtYXJrIHRoZSBlbmQgb2YgYWxsIHByb2JsZW0gZGVzY3JpcHRpb25zLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHNldCBvZiB1bml0cywgcHJvZHVjZSBvbmUgbGluZSBvZiBvdXRwdXQgdGhhdCBjb250YWlucyB0aGUgZXF1aXZhbGVudCBjb252ZXJzaW9ucy4gVGhlIGNvbnZlcnNpb25zIHNob3VsZCBiZSBzb3J0ZWQgbGVmdCB0byByaWdodCwgd2l0aCB0aGUgbGFyZ2VzdCB1bml0IGFwcGVhcmluZyBvbiB0aGUgbGVmdC4gVGhlIGNvbnZlcnNpb24gZmFjdG9ycyBzaG91bGQgYmUgZGVmaW5lZCB3aXRoIHJlc3BlY3QgdG8gdGhlIGxlZnRtb3N0IHVuaXQgKGkuZS4sIHRoZSBsYXJnZXN0IHVuaXQpIGFuZCBzaG91bGQgYmUgc2VwYXJhdGVkIGJ5ICZxdW90OyA9ICZxdW90Oy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

ICPC > Regionals > North America > North America Qualification Contest > ACM-ICPC North America Qualifier 2014 J번

  • 문제를 번역한 사람: jh05013, tae
  • 문제를 만든 사람: Mike Zmuda