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

문제

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

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

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

  • 노래 "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+XHViMTc4XHViNzk4ICZxdW90O1RpIERhIEJ1IERpIEJ1IERhJnF1b3Q7XHViMjk0IHRvcDNcdWIxNzhcdWI3OThcdWM5MTEgXHVkNTU4XHViMDk4XHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWIxNzhcdWI3OTggJnF1b3Q7VHJlYmEgbWkgbmUmc2Nhcm9uO3RvIGphXHUwMTBkZSBvZCBzbmEmcXVvdDtcdWM2NDAgXHViMTc4XHViNzk4ICZxdW90O0phIHNlIGtvbmphIGJvamltJnF1b3Q7XHVjNzQwIHRvcDJcdWIxNzhcdWI3OThcdWM1ZDAgXHVjMThkXHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YzcwNCBcdWM5YzRcdWMyMjBcdWI0ZTRcdWM3NDAmbmJzcDtcdWM1YjRcdWIyOTBcdWFjODNcdWIzYzQgXHVjODE1XHVkNjU1XHVkNzg4IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YzljMCBcdWM1NGFcdWM5YzBcdWI5Y2MsIFx1YjE3OFx1Yjc5OCAmcXVvdDtUaSBEYSBCdSBEaSBCdSBEYSZxdW90O1x1YWMwMCBcdWI5YWNcdWMyYTRcdWQyYjhcdWM3NTggXHVjMTM4IFx1YmM4OFx1YzlmOCBcdWM3MDRcdWNlNThcdWM1ZDAgXHVjNjI4XHViMmU0XHViMjk0IFx1YWM4M1x1Yzc0MCBcdWNkOTRcdWI4NjBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjOWM0XHVjMjIwXHViNGU0XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NFx1YjU0YywmbmJzcDsgXHViOWFjXHVjMmE0XHVkMmI4XHVjNWQwXHVjMTFjIFx1YzgxNVx1ZDY1NVx1ZDU1YyBcdWM3MDRcdWNlNThcdWI5N2MgXHVjZDk0XHViODYwXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYWE4XHViNGUwIFx1YjE3OFx1Yjc5OFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM5YzRcdWMyMjBcdWM3NTggXHVjMjE4XHVhYzAwIFx1YzgxNVx1YzIxOCBOXHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgNTAwICk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjXHVjNzU4IFx1YWMwMSBOXHVjOTA0XHVjNWQwXHViMjk0ICZxdW90O0Egb2QgQiBzb25nMSBzb25nMiAuLi4gc29uZ0EmcXVvdDsgXHVkNjE1XHVkMGRjXHVjNzU4IFx1YzljNFx1YzIyMFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YjI5NCAmcXVvdDtzb25nMSZxdW90OywgJnF1b3Q7c29uZzImcXVvdDssIC4uLiAmcXVvdDtzb25nQSZxdW90O1x1YWMwMCBcdWI5YWNcdWMyYTRcdWQyYjhcdWM3NTggdG9wIEJcdWM1ZDAgXHVjMThkXHVkNTVjXHViMmU0XHViMjk0IFx1Yzc1OFx1YmJmOFx1Yzc3NFx1YjJlNC4gKDEgJmxlOyBBICZsZTsgQiAmbGU7IDEwMCk8XC9wPlxyXG5cclxuPHA+XHVhYzAxXHVhYzAxXHVjNzU4IFx1YjE3OFx1Yjc5OCBcdWM3NzRcdWI5ODRcdWM3NDAgXHVkNTU4XHViMDk4XHVjNzU4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NFx1YWNlMCwgXHVjZDVjXHViMzAwIDIwXHVhYzFjXHVjNzU4IFx1YzYwMVx1YmIzOCBcdWM1NGNcdWQzMGNcdWJjYjMgXHVjMThjXHViYjM4XHVjNzkwXHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxY1x1YjJlNC4gXHVjOWM0XHVjMjIwXHVjNWQwXHVjMTFjIFx1YjA5OFx1ZDBjMFx1YjA5OFx1YjI5NCBcdWIyZTRcdWI5NzggXHViMTc4XHViNzk4XHVjNzU4IFx1YzgwNFx1Y2NiNCBcdWMyMThcdWIyOTQgXHVjZDVjXHViMzAwIDUwMFx1YWMxY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+Tm90ZTogXHVjOWM0XHVjMjIwXHViNGU0XHVjNzQwIFx1YzExY1x1Yjg1YyBcdWJhYThcdWMyMWNcdWI0MThcdWM5YzAgXHVjNTRhXHVjNzNjXHViYTcwLCBcdWM4MTVcdWQ2NTVcdWQ1NWMgXHVjNzA0XHVjZTU4XHViOTdjIFx1Y2Q5NFx1Yjg2MFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YjE3OFx1Yjc5OFx1YWMwMCBcdWM4MDFcdWM1YjRcdWIzYzQgXHVkNTVjXHVhYzFjXHViMjk0IFx1Yzg3NFx1YzdhY1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWI5YWNcdWMyYTRcdWQyYjhcdWM1ZDBcdWMxMWMgXHVhZGY4XHViNGU0XHVjNzU4IFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWNkOTRcdWI4NjBcdWI0MjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHViMTc4XHViNzk4XHViNGU0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1Yjc3Yy4gXHVhY2IwXHVhY2ZjXHViMjk0IFx1YWMwMSBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5ICZxdW90O3Bvc2l0aW9uIHNvbmcmcXVvdDtcdWM3NTggXHVkNjE1XHVkMGRjXHViODVjIHBvc2l0aW9uXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWM2MjRcdWI5ODRcdWNjMjhcdWMyMWNcdWM3M2NcdWI4NWMgXHVjZDljXHViODI1XHViNDE4XHVjNWI0XHVjNTdjXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMxNTYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJ0b3BsaXN0YSIsImRlc2NyaXB0aW9uIjoiPHA+QXQgdGhlIGVuZCBvZiB0aGUgeWVhciwgYSBwb3B1bGFyIHJhZGlvIHN0YXRpb24gcHVibGlzaGVzIGEgbGlzdCBvZiBzb25ncywgcmFua2VkIGJ5IGxpc3RlbmVycyYjMzk7IHZvdGVzIHRocm91Z2hvdXQgdGhlIHllYXIuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBzdGF0aW9uIGtlZXBzIHRoZSBsaXN0IGNvbmZpZGVudGlhbCBmb3IgYSB3aGlsZSwgYW5kIG9yZ2FuaXplcyBhIGd1ZXNzaW5nIGNvbXBldGl0aW9uIGZvciB0aGUgbGlzdGVuZXJzLiBUaGV5IGFubm91bmNlIGNlcnRhaW4gaGludHMgYWJvdXQgdGhlIHBsYWNlbWVudCBvZiBzb21lIHNvbmdzIGFuZCBhc2sgdGhlIGxpc3RlbmVycyB0byBkZWR1Y2UgdGhlIGV4YWN0IHBvc2l0aW9ucyBvZiBhcyBtYW55IHNvbmdzIGFzIHBvc3NpYmxlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgY29uc2lkZXIgdGhlIGZvbGxvd2luZyB0d28gc3RhdGVtZW50czombmJzcDs8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5UaGUgc29uZyAmcXVvdDtUaSBEYSBCdSBEaSBCdSBEYSZxdW90OyBpcyBvbmUgb2YgdGhlIHRvcCB0aHJlZSBzb25ncy4mbmJzcDs8XC9saT5cclxuXHQ8bGk+U29uZ3MgJnF1b3Q7VHJlYmEgbWkgbmUmc2Nhcm9uO3RvIGphXHUwMTBkZSBvZCBzbmEmcXVvdDsgYW5kICZxdW90O0phIHNlIGtvbmphIGJvamltJnF1b3Q7IGFyZSBhbW9uZyB0aGUgdG9wIHR3byBzb25ncy4mbmJzcDs8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5UaGV5IGRvbiYjMzk7dCByZXZlYWwgYW55dGhpbmcgZGlyZWN0bHksIGJ1dCBvbmUgY2FuIHN0aWxsIGRlZHVjZSB0aGF0IHRoZSBzb25nICZxdW90O1RpIERhIEJ1IERpIEJ1IERhJnF1b3Q7IGNvbWVzIGluIHRoaXJkIG9uIHRoZSBsaXN0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCwgZ2l2ZW4gYSBudW1iZXIgb2Ygc3RhdGVtZW50cywgb3V0cHV0cyBhbGwgc29uZ3Mgd2hvc2UgZXhhY3QgcG9zaXRpb24gb24gdGhlIGxpc3QgY2FuIGJlIGRlZHVjZWQuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhbiBpbnRlZ2VyIE4sIDEgJmxlOyBOICZsZTsgNTAwLCB0aGUgbnVtYmVyIG9mIHN0YXRlbWVudHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW5zIGEgc3RhdGVtZW50IG9mIHRoZSBmb3JtICZxdW90O0Egb2QgQiBzb25nMSBzb25nMiAuLi4gc29uZ0EmcXVvdDssIDEgJmxlOyBBICZsZTsgQiAmbGU7IDEwMCwgbWVhbmluZyB0aGF0IHRoZSBzb25ncyAmcXVvdDtzb25nMSZxdW90OywgLi4uLCAmcXVvdDtzb25nQSZxdW90OyBhcmUgYW1vbmcgdGhlIHRvcCBCIHNvbmdzIG9uIHRoZSBsaXN0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIHNvbmcgbmFtZSBpcyBhIHN0cmluZywgY29uc2lzdGluZyBvZiBhdCBtb3N0IDIwIGxvd2VyY2FzZSBsZXR0ZXJzIG9mIEVuZ2xpc2ggYWxwaGFiZXQgKCYjMzk7YSYjMzk7LSYjMzk7eiYjMzk7KS4gVGhlIHRvdGFsIG51bWJlciBvZiBkaWZmZXJlbnQgc29uZ3MgYWNyb3NzIGFsbCBzdGF0ZW1lbnRzIHdpbGwgYmUgYXQgbW9zdCA1MDAuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk5vdGU6IHRoZSBzdGF0ZW1lbnRzIHdpbGwgbm90IGNvbnRyYWRpY3QgZWFjaCBvdGhlciBhbmQgdGhlcmUgd2lsbCBiZSBhdCBsZWFzdCBvbmUgc29uZyB3aG9zZSBleGFjdCBwb3NpdGlvbiBjYW4gYmUgZGVkdWNlZC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgYWxsIHNvbmdzIHdob3NlIHBvc2l0aW9uIG9uIHRoZSBsaXN0IGNhbiBiZSBkZWR1Y2VkLiBUaGUgcmVzdWx0IHNob3VsZCBiZSBwcmludGVkIGluIHRoZSBmb3JtICZxdW90O3Bvc2l0aW9uIHNvbmcmcXVvdDssIHNvcnRlZCBpbiBhc2NlbmRpbmcgb3JkZXIgYnkgcG9zaXRpb24sIGVhY2ggc29uZyBvbiBpdHMgb3duIGxpbmUuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d