시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 3 2 2 66.667%

문제

연말에, 한 유명한 라디오 스테이션이 그 해에 걸쳐 청자들의 투표로 인해 랭크된 노래 목록을 출판한다.

스테이션은 그 목록을 잠시동안 안전하게 지키고, 청자들을 위한 추론 경합을 개최한다. 그들은 몇몇 노래의 배치에 대한 특정한 힌트를 발표한다. 그리고 청자들이 가능한 많은 노래의 정확한 위치를 추론하도록 한다.

예를 들어, 다음 두 진술을 고려해보자:

  • 노래 "Ti Da Bu Di Bu Da"는 top3노래중 하나이다.
  • 노래 "Treba mi nešto jače od sna"와 노래 "Ja se konja bojim"은 top2노래에 속한다.

위 진술들은 어느것도 정확히 나타내지 않지만, 노래 "Ti Da Bu Di Bu Da"가 리스트의 세번째 위치에 온다는 것은 추론할 수 있다.

진술들이 주어졌을때,  리스트에서 정확한 위치를 추론할 수 있는 모든 노래를 출력하는 프로그램을 작성하라.

입력

입력의 첫번째 줄에는 진술의 수가 정수 N으로 주어진다. (1 ≤ N ≤ 500 )

다음의 각 N줄에는 "A od B song1 song2 ... songA" 형태의 진술이 주어진다. 이는 "song1", "song2", ... "songA"가 리스트의 top B에 속한다는 의미이다. (1 ≤ A ≤ B ≤ 100)

각각의 노래 이름은 하나의 문자열이고, 최대 20개의 영문 알파벳 소문자로 구성된다. 진술에서 나타나는 다른 노래의 전체 수는 최대 500개이다.

Note: 진술들은 서로 모순되지 않으며, 정확한 위치를 추론할 수 있는 노래가 적어도 한개는 존재한다.

출력

리스트에서 그들의 위치가 추론될 수 있는 모든 노래들을 출력하라. 결과는 각 줄에 하나씩 "position song"의 형태로 position에 대한 오름차순으로 출력되어야한다.

예제 입력 1

2
1 od 3 tidabu
2 od 2 trebami jasekonja

예제 출력 1

3 tidabu
W3sicHJvYmxlbV9pZCI6IjMxNTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIxNzhcdWI3OTgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzVmMFx1YjlkMFx1YzVkMCwgXHVkNTVjIFx1YzcyMFx1YmE4NVx1ZDU1YyBcdWI3N2NcdWI1MTRcdWM2MjQgXHVjMmE0XHVkMTRjXHVjNzc0XHVjMTU4XHVjNzc0IFx1YWRmOCBcdWQ1NzRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1Y2NhZFx1Yzc5MFx1YjRlNFx1Yzc1OCBcdWQyMmNcdWQ0NWNcdWI4NWMgXHVjNzc4XHVkNTc0IFx1YjdhZFx1ZDA2Y1x1YjQxYyBcdWIxNzhcdWI3OTggXHViYWE5XHViODVkXHVjNzQ0IFx1Y2Q5Y1x1ZDMxMFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMmE0XHVkMTRjXHVjNzc0XHVjMTU4XHVjNzQwIFx1YWRmOCBcdWJhYTlcdWI4NWRcdWM3NDQgXHVjN2EwXHVjMmRjXHViM2Q5XHVjNTQ4IFx1YzU0OFx1YzgwNFx1ZDU1OFx1YWM4YyBcdWM5YzBcdWQwYTRcdWFjZTAsIFx1Y2NhZFx1Yzc5MFx1YjRlNFx1Yzc0NCBcdWM3MDRcdWQ1NWMgXHVjZDk0XHViODYwIFx1YWNiZFx1ZDU2OVx1Yzc0NCBcdWFjMWNcdWNkNWNcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjRlNFx1Yzc0MCBcdWJhODdcdWJhODcgXHViMTc4XHViNzk4XHVjNzU4IFx1YmMzMFx1Y2U1OFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVkMmI5XHVjODE1XHVkNTVjIFx1ZDc4Y1x1ZDJiOFx1Yjk3YyBcdWJjMWNcdWQ0NWNcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWNjYWRcdWM3OTBcdWI0ZTRcdWM3NzQgXHVhYzAwXHViMmE1XHVkNTVjIFx1YjljZVx1Yzc0MCBcdWIxNzhcdWI3OThcdWM3NTggXHVjODE1XHVkNjU1XHVkNTVjIFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWNkOTRcdWI4NjBcdWQ1NThcdWIzYzRcdWI4NWQgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWIyZTRcdWM3NGMgXHViNDUwIFx1YzljNFx1YzIyMFx1Yzc0NCBcdWFjZTBcdWI4MjRcdWQ1NzRcdWJjZjRcdWM3OTA6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHViMTc4XHViNzk4ICZxdW90O1RpIERhIEJ1IERpIEJ1IERhJnF1b3Q7XHViMjk0IHRvcDNcdWIxNzhcdWI3OThcdWM5MTEgXHVkNTU4XHViMDk4XHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWIxNzhcdWI3OTggJnF1b3Q7VHJlYmEgbWkgbmUmc2Nhcm9uO3RvIGphXHUwMTBkZSBvZCBzbmEmcXVvdDtcdWM2NDAgXHViMTc4XHViNzk4ICZxdW90O0phIHNlIGtvbmphIGJvamltJnF1b3Q7XHVjNzQwIHRvcDJcdWIxNzhcdWI3OThcdWM1ZDAgXHVjMThkXHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YzcwNCBcdWM5YzRcdWMyMjBcdWI0ZTRcdWM3NDAmbmJzcDtcdWM1YjRcdWIyOTBcdWFjODNcdWIzYzQgXHVjODE1XHVkNjU1XHVkNzg4IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YzljMCBcdWM1NGFcdWM5YzBcdWI5Y2MsIFx1YjE3OFx1Yjc5OCAmcXVvdDtUaSBEYSBCdSBEaSBCdSBEYSZxdW90O1x1YWMwMCBcdWI5YWNcdWMyYTRcdWQyYjhcdWM3NTggXHVjMTM4XHViYzg4XHVjOWY4IFx1YzcwNFx1Y2U1OFx1YzVkMCBcdWM2MjhcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzQwIFx1Y2Q5NFx1Yjg2MFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM5YzRcdWMyMjBcdWI0ZTRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0XHViNTRjLCZuYnNwOyBcdWI5YWNcdWMyYTRcdWQyYjhcdWM1ZDBcdWMxMWMgXHVjODE1XHVkNjU1XHVkNTVjIFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWNkOTRcdWI4NjBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHViMTc4XHViNzk4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1Y2NhYlx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjOWM0XHVjMjIwXHVjNzU4IFx1YzIxOFx1YWMwMCBcdWM4MTVcdWMyMTggTlx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDUwMCApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0Y1x1Yzc1OCBcdWFjMDEgTlx1YzkwNFx1YzVkMFx1YjI5NCAmcXVvdDtBIG9kIEIgc29uZzEgc29uZzIgLi4uIHNvbmdBJnF1b3Q7IFx1ZDYxNVx1ZDBkY1x1Yzc1OCBcdWM5YzRcdWMyMjBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWIyOTQgJnF1b3Q7c29uZzEmcXVvdDssICZxdW90O3NvbmcyJnF1b3Q7LCAuLi4gJnF1b3Q7c29uZ0EmcXVvdDtcdWFjMDAgXHViOWFjXHVjMmE0XHVkMmI4XHVjNzU4IHRvcCBCXHVjNWQwIFx1YzE4ZFx1ZDU1Y1x1YjJlNFx1YjI5NCBcdWM3NThcdWJiZjhcdWM3NzRcdWIyZTQuICgxICZsZTsgQSAmbGU7IEIgJmxlOyAxMDApPFwvcD5cclxuXHJcbjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWIxNzhcdWI3OTggXHVjNzc0XHViOTg0XHVjNzQwIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzRcdWFjZTAsIFx1Y2Q1Y1x1YjMwMCAyMFx1YWMxY1x1Yzc1OCBcdWM2MDFcdWJiMzggXHVjNTRjXHVkMzBjXHViY2IzIFx1YzE4Y1x1YmIzOFx1Yzc5MFx1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MWNcdWIyZTQuIFx1YzljNFx1YzIyMFx1YzVkMFx1YzExYyBcdWIwOThcdWQwYzBcdWIwOThcdWIyOTQgXHViMmU0XHViOTc4IFx1YjE3OFx1Yjc5OFx1Yzc1OCBcdWM4MDRcdWNjYjQgXHVjMjE4XHViMjk0IFx1Y2Q1Y1x1YjMwMCA1MDBcdWFjMWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPk5vdGU6IFx1YzljNFx1YzIyMFx1YjRlNFx1Yzc0MCBcdWMxMWNcdWI4NWMgXHViYWE4XHVjMjFjXHViNDE4XHVjOWMwIFx1YzU0YVx1YzczY1x1YmE3MCwgXHVjODE1XHVkNjU1XHVkNTVjIFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWNkOTRcdWI4NjBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWIxNzhcdWI3OThcdWFjMDAgXHVjODAxXHVjNWI0XHViM2M0IFx1ZDU1Y1x1YWMxY1x1YjI5NCBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViOWFjXHVjMmE0XHVkMmI4XHVjNWQwXHVjMTFjIFx1YWRmOFx1YjRlNFx1Yzc1OCBcdWM3MDRcdWNlNThcdWFjMDAgXHVjZDk0XHViODYwXHViNDIwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYWE4XHViNGUwIFx1YjE3OFx1Yjc5OFx1YjRlNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWI3N2MuIFx1YWNiMFx1YWNmY1x1YjI5NCBcdWFjMDEgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSAmcXVvdDtwb3NpdGlvbiBzb25nJnF1b3Q7XHVjNzU4IFx1ZDYxNVx1ZDBkY1x1Yjg1YyBwb3NpdGlvblx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjNjI0XHViOTg0XHVjYzI4XHVjMjFjXHVjNzNjXHViODVjIFx1Y2Q5Y1x1YjgyNVx1YjQxOFx1YzViNFx1YzU3Y1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMTU2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoidG9wbGlzdGEiLCJkZXNjcmlwdGlvbiI6IjxwPkF0IHRoZSBlbmQgb2YgdGhlIHllYXIsIGEgcG9wdWxhciByYWRpbyBzdGF0aW9uIHB1Ymxpc2hlcyBhIGxpc3Qgb2Ygc29uZ3MsIHJhbmtlZCBieSBsaXN0ZW5lcnMmIzM5OyB2b3RlcyB0aHJvdWdob3V0IHRoZSB5ZWFyLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgc3RhdGlvbiBrZWVwcyB0aGUgbGlzdCBjb25maWRlbnRpYWwgZm9yIGEgd2hpbGUsIGFuZCBvcmdhbml6ZXMgYSBndWVzc2luZyBjb21wZXRpdGlvbiBmb3IgdGhlIGxpc3RlbmVycy4gVGhleSBhbm5vdW5jZSBjZXJ0YWluIGhpbnRzIGFib3V0IHRoZSBwbGFjZW1lbnQgb2Ygc29tZSBzb25ncyBhbmQgYXNrIHRoZSBsaXN0ZW5lcnMgdG8gZGVkdWNlIHRoZSBleGFjdCBwb3NpdGlvbnMgb2YgYXMgbWFueSBzb25ncyBhcyBwb3NzaWJsZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIGNvbnNpZGVyIHRoZSBmb2xsb3dpbmcgdHdvIHN0YXRlbWVudHM6Jm5ic3A7PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+VGhlIHNvbmcgJnF1b3Q7VGkgRGEgQnUgRGkgQnUgRGEmcXVvdDsgaXMgb25lIG9mIHRoZSB0b3AgdGhyZWUgc29uZ3MuJm5ic3A7PFwvbGk+XHJcblx0PGxpPlNvbmdzICZxdW90O1RyZWJhIG1pIG5lJnNjYXJvbjt0byBqYVx1MDEwZGUgb2Qgc25hJnF1b3Q7IGFuZCAmcXVvdDtKYSBzZSBrb25qYSBib2ppbSZxdW90OyBhcmUgYW1vbmcgdGhlIHRvcCB0d28gc29uZ3MuJm5ic3A7PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+VGhleSBkb24mIzM5O3QgcmV2ZWFsIGFueXRoaW5nIGRpcmVjdGx5LCBidXQgb25lIGNhbiBzdGlsbCBkZWR1Y2UgdGhhdCB0aGUgc29uZyAmcXVvdDtUaSBEYSBCdSBEaSBCdSBEYSZxdW90OyBjb21lcyBpbiB0aGlyZCBvbiB0aGUgbGlzdC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQsIGdpdmVuIGEgbnVtYmVyIG9mIHN0YXRlbWVudHMsIG91dHB1dHMgYWxsIHNvbmdzIHdob3NlIGV4YWN0IHBvc2l0aW9uIG9uIHRoZSBsaXN0IGNhbiBiZSBkZWR1Y2VkLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYW4gaW50ZWdlciBOLCAxICZsZTsgTiAmbGU7IDUwMCwgdGhlIG51bWJlciBvZiBzdGF0ZW1lbnRzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyBjb250YWlucyBhIHN0YXRlbWVudCBvZiB0aGUgZm9ybSAmcXVvdDtBIG9kIEIgc29uZzEgc29uZzIgLi4uIHNvbmdBJnF1b3Q7LCAxICZsZTsgQSAmbGU7IEIgJmxlOyAxMDAsIG1lYW5pbmcgdGhhdCB0aGUgc29uZ3MgJnF1b3Q7c29uZzEmcXVvdDssIC4uLiwgJnF1b3Q7c29uZ0EmcXVvdDsgYXJlIGFtb25nIHRoZSB0b3AgQiBzb25ncyBvbiB0aGUgbGlzdC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBzb25nIG5hbWUgaXMgYSBzdHJpbmcsIGNvbnNpc3Rpbmcgb2YgYXQgbW9zdCAyMCBsb3dlcmNhc2UgbGV0dGVycyBvZiBFbmdsaXNoIGFscGhhYmV0ICgmIzM5O2EmIzM5Oy0mIzM5O3omIzM5OykuIFRoZSB0b3RhbCBudW1iZXIgb2YgZGlmZmVyZW50IHNvbmdzIGFjcm9zcyBhbGwgc3RhdGVtZW50cyB3aWxsIGJlIGF0IG1vc3QgNTAwLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Ob3RlOiB0aGUgc3RhdGVtZW50cyB3aWxsIG5vdCBjb250cmFkaWN0IGVhY2ggb3RoZXIgYW5kIHRoZXJlIHdpbGwgYmUgYXQgbGVhc3Qgb25lIHNvbmcgd2hvc2UgZXhhY3QgcG9zaXRpb24gY2FuIGJlIGRlZHVjZWQuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IGFsbCBzb25ncyB3aG9zZSBwb3NpdGlvbiBvbiB0aGUgbGlzdCBjYW4gYmUgZGVkdWNlZC4gVGhlIHJlc3VsdCBzaG91bGQgYmUgcHJpbnRlZCBpbiB0aGUgZm9ybSAmcXVvdDtwb3NpdGlvbiBzb25nJnF1b3Q7LCBzb3J0ZWQgaW4gYXNjZW5kaW5nIG9yZGVyIGJ5IHBvc2l0aW9uLCBlYWNoIHNvbmcgb24gaXRzIG93biBsaW5lLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==