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

문제

주식회사 월드에서는 오랫동안 열심히 일을 하면 그에 따라 승진할 수도 있고, 그만큼 많은 급료를 받을 수도 있다.

즉, 어떤 사원의 상사는 적어도 그 사원만큼은 회사에서 근무한 것이고, 그 사원보다 많은 급료를 받는다. 또, 어느 사원의 직속 상사는, 적어도 그 사원만큼 회사에서 근무했고, 그 사원보다 많은 급료를 받는 사람들 중에서 가장 적은 급료를 받는 사람이다.

어느 사원의 직속 상사에게 있어서, 그 사원은 부하가 된다. 어떤 사원의 부하의 부하들도 모두 그 사원의 부하라 하자. 만약에 어느 사원이 누구의 상사도 아니면 그 사원은 부하가 없다.

주식회사 월드의 상사-부하 관계가 위와 같이 정의될 때, 몇몇 사원의 직속 상사와 부하의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 n(≤30,000), m(≤200)이 주어진다. n은 사원의 수고, m은 우리가 직속 상사와 부하의 수를 알아보려는 사원의 수이다. 다음 n개의 줄에는 각 사원의 정보를 나타내는 세 정수 a, b, c가 주어진다. a(int 범위)는 사원의 ID, b(0≤b≤10,000,000)는 급료, c(1,000,000≤c≤2,500,000)는 근무한 시간(분 단위)을 나타낸다. 다음 m개의 줄에는 직속 상사와 부하의 수를 알아보려는 사원의 ID가 주어진다.

출력

m개의 줄에 입력된 순서대로 해당 사원의 직속 상사의 ID와 부하의 수를 출력한다. 만약 입력으로 주어진 ID가 사장일 경우, 즉 가장 오래 근무하였고 가장 많은 급료를 받는 사원의 ID일 경우에는 직속 상사의 ID 대신에 0을 출력한다(직속 상사가 없으므로).

예제 입력 1

3 3
123456 14323 1700000
123458 41412 1900000
123457 15221 1800000
123456
123458
123457

예제 출력 1

123457 0
0 2
123458 1
W3sicHJvYmxlbV9pZCI6IjIzMTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYzFcdWMwYWMgXHVjYzNlXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM4ZmNcdWMyZGRcdWQ2OGNcdWMwYWMgXHVjNmQ0XHViNGRjXHVjNWQwXHVjMTFjXHViMjk0IFx1YzYyNFx1YjdhYlx1YjNkOVx1YzU0OCBcdWM1ZjRcdWMyZWNcdWQ3ODggXHVjNzdjXHVjNzQ0IFx1ZDU1OFx1YmE3NCBcdWFkZjhcdWM1ZDAgXHViNTMwXHViNzdjIFx1YzJiOVx1YzljNFx1ZDU2MCBcdWMyMThcdWIzYzQgXHVjNzg4XHVhY2UwLCBcdWFkZjhcdWI5Y2NcdWQwN2MgXHViOWNlXHVjNzQwIFx1YWUwOVx1YjhjY1x1Yjk3YyBcdWJjMWJcdWM3NDQgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG48cD5cdWM5ODksIFx1YzViNFx1YjVhNCBcdWMwYWNcdWM2ZDBcdWM3NTggXHVjMGMxXHVjMGFjXHViMjk0IFx1YzgwMVx1YzViNFx1YjNjNCBcdWFkZjggXHVjMGFjXHVjNmQwXHViOWNjXHVkMDdjXHVjNzQwIFx1ZDY4Y1x1YzBhY1x1YzVkMFx1YzExYyBcdWFkZmNcdWJiMzRcdWQ1NWMgXHVhYzgzXHVjNzc0XHVhY2UwLCBcdWFkZjggXHVjMGFjXHVjNmQwXHViY2Y0XHViMmU0IFx1YjljZVx1Yzc0MCBcdWFlMDlcdWI4Y2NcdWI5N2MgXHViYzFiXHViMjk0XHViMmU0LiBcdWI2MTAsIFx1YzViNFx1YjI5MCBcdWMwYWNcdWM2ZDBcdWM3NTggXHVjOWMxXHVjMThkIFx1YzBjMVx1YzBhY1x1YjI5NCwgXHVjODAxXHVjNWI0XHViM2M0IFx1YWRmOCBcdWMwYWNcdWM2ZDBcdWI5Y2NcdWQwN2MgXHVkNjhjXHVjMGFjXHVjNWQwXHVjMTFjIFx1YWRmY1x1YmIzNFx1ZDU4OFx1YWNlMCwgXHVhZGY4IFx1YzBhY1x1YzZkMFx1YmNmNFx1YjJlNCBcdWI5Y2VcdWM3NDAgXHVhZTA5XHViOGNjXHViOTdjIFx1YmMxYlx1YjI5NCBcdWMwYWNcdWI3OGNcdWI0ZTQgXHVjOTExXHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWM4MDFcdWM3NDAgXHVhZTA5XHViOGNjXHViOTdjIFx1YmMxYlx1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NzRcdWIyZTQuPFwvcD5cclxuPHA+XHVjNWI0XHViMjkwIFx1YzBhY1x1YzZkMFx1Yzc1OCBcdWM5YzFcdWMxOGQgXHVjMGMxXHVjMGFjXHVjNWQwXHVhYzhjIFx1Yzc4OFx1YzViNFx1YzExYywgXHVhZGY4IFx1YzBhY1x1YzZkMFx1Yzc0MCBcdWJkODBcdWQ1NThcdWFjMDAgXHViNDFjXHViMmU0LiBcdWM1YjRcdWI1YTQgXHVjMGFjXHVjNmQwXHVjNzU4IFx1YmQ4MFx1ZDU1OFx1Yzc1OCBcdWJkODBcdWQ1NThcdWI0ZTRcdWIzYzQgXHViYWE4XHViNDUwIFx1YWRmOCBcdWMwYWNcdWM2ZDBcdWM3NTggXHViZDgwXHVkNTU4XHViNzdjIFx1ZDU1OFx1Yzc5MC4gXHViOWNjXHVjNTdkXHVjNWQwIFx1YzViNFx1YjI5MCBcdWMwYWNcdWM2ZDBcdWM3NzQgXHViMjA0XHVhZDZjXHVjNzU4IFx1YzBjMVx1YzBhY1x1YjNjNCBcdWM1NDRcdWIyYzhcdWJhNzQgXHVhZGY4IFx1YzBhY1x1YzZkMFx1Yzc0MCBcdWJkODBcdWQ1NThcdWFjMDAgXHVjNWM2XHViMmU0LjxcL3A+XHJcbjxwPlx1YzhmY1x1YzJkZFx1ZDY4Y1x1YzBhYyBcdWM2ZDRcdWI0ZGNcdWM3NTggXHVjMGMxXHVjMGFjLVx1YmQ4MFx1ZDU1OCBcdWFkMDBcdWFjYzRcdWFjMDAgXHVjNzA0XHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWM4MTVcdWM3NThcdWI0MjAgXHViNTRjLCBcdWJhODdcdWJhODcgXHVjMGFjXHVjNmQwXHVjNzU4IFx1YzljMVx1YzE4ZCBcdWMwYzFcdWMwYWNcdWM2NDAgXHViZDgwXHVkNTU4XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWI0NTAgXHVjODE1XHVjMjE4IG4oJmxlOzMwLDAwMCksIG0oJmxlOzIwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBuXHVjNzQwIFx1YzBhY1x1YzZkMFx1Yzc1OCBcdWMyMThcdWFjZTAsIG1cdWM3NDAgXHVjNmIwXHViOWFjXHVhYzAwIFx1YzljMVx1YzE4ZCBcdWMwYzFcdWMwYWNcdWM2NDAgXHViZDgwXHVkNTU4XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWM1NGNcdWM1NDRcdWJjZjRcdWI4MjRcdWIyOTQgXHVjMGFjXHVjNmQwXHVjNzU4IFx1YzIxOFx1Yzc3NFx1YjJlNC4gXHViMmU0XHVjNzRjIG5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWMwYWNcdWM2ZDBcdWM3NTggXHVjODE1XHViY2Y0XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWMxMzggXHVjODE1XHVjMjE4IGEsIGIsIGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBhKGludCBcdWJjOTRcdWM3MDQpXHViMjk0IFx1YzBhY1x1YzZkMFx1Yzc1OCBJRCwgYigwJmxlO2ImbGU7MTAsMDAwLDAwMClcdWIyOTQgXHVhZTA5XHViOGNjLCBjKDEsMDAwLDAwMCZsZTtjJmxlOzIsNTAwLDAwMClcdWIyOTQgXHVhZGZjXHViYjM0XHVkNTVjIFx1YzJkY1x1YWMwNChcdWJkODQgXHViMmU4XHVjNzA0KVx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuIFx1YjJlNFx1Yzc0YyBtXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM5YzFcdWMxOGQgXHVjMGMxXHVjMGFjXHVjNjQwIFx1YmQ4MFx1ZDU1OFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjNTRjXHVjNTQ0XHViY2Y0XHViODI0XHViMjk0IFx1YzBhY1x1YzZkMFx1Yzc1OCBJRFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD4iLCJvdXRwdXQiOiI8cD5tXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWM3ODVcdWI4MjVcdWI0MWMgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1ZDU3NFx1YjJmOSBcdWMwYWNcdWM2ZDBcdWM3NTggXHVjOWMxXHVjMThkIFx1YzBjMVx1YzBhY1x1Yzc1OCBJRFx1YzY0MCBcdWJkODBcdWQ1NThcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgSURcdWFjMDAgXHVjMGFjXHVjN2E1XHVjNzdjIFx1YWNiZFx1YzZiMCwgXHVjOTg5IFx1YWMwMFx1YzdhNSBcdWM2MjRcdWI3OTggXHVhZGZjXHViYjM0XHVkNTU4XHVjNjAwXHVhY2UwIFx1YWMwMFx1YzdhNSBcdWI5Y2VcdWM3NDAgXHVhZTA5XHViOGNjXHViOTdjIFx1YmMxYlx1YjI5NCBcdWMwYWNcdWM2ZDBcdWM3NTggSURcdWM3N2MgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YzljMVx1YzE4ZCBcdWMwYzFcdWMwYWNcdWM3NTggSUQgXHViMzAwXHVjMmUwXHVjNWQwIDBcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0KFx1YzljMVx1YzE4ZCBcdWMwYzFcdWMwYWNcdWFjMDAgXHVjNWM2XHVjNzNjXHViYmMwXHViODVjKS48XC9wPiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjMxOCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ildob1x1MjAxOXMgdGhlIGJvc3M/IiwiZGVzY3JpcHRpb24iOiI8cD5TZXZlcmFsIHN1cnZleXMgaW5kaWNhdGUgdGhhdCB0aGUgdGFsbGVyIHlvdSBhcmUsIHRoZSBoaWdoZXIgeW91IGNhbiBjbGltYiB0aGUgY29ycG9yYXRlIGxhZGRlci4gQXQgVEFMTCBFbnRlcnByaXNlcyBJbmMuIHRoaXMgJmxkcXVvO2RlIGZhY3RvIHN0YW5kYXJkJnJkcXVvOyBoYXMgYmVlbiBwcm9wZXJseSBmb3JtYWxpemVkOiB5b3VyIGJvc3MgaXMgYWx3YXlzIGF0IGxlYXN0IGFzIHRhbGwgYXMgeW91IGFyZS4gRnVydGhlcm1vcmUsIHlvdSBjYW4gc2FmZWx5IGFzc3VtZSB0aGF0IHlvdXIgYm9zcyBlYXJucyBhIGJpdCBtb3JlIHRoYW4geW91IGRvLiBJbiBmYWN0LCB5b3UgY2FuIGJlIGFic29sdXRlbHkgc3VyZSB0aGF0IHlvdXIgaW1tZWRpYXRlIGJvc3MgaXMgdGhlIHBlcnNvbiB3aG8gZWFybnMgdGhlIGxlYXN0IGFtb25nIGFsbCB0aGUgZW1wbG95ZWVzIHRoYXQgZWFybiBtb3JlIHRoYW4geW91IGFuZCBhcmUgYXQgbGVhc3QgYXMgdGFsbCBhcyB5b3UgYXJlLiBGdXJ0aGVybW9yZSwgaWYgeW91IGFyZSB0aGUgaW1tZWRpYXRlIGJvc3Mgb2Ygc29tZW9uZSwgdGhhdCBwZXJzb24gaXMgeW91ciBzdWJvcmRpbmF0ZSwgYW5kIGFsbCBoaXMgc3Vib3JkaW5hdGVzIGFyZSB5b3VyIHN1Ym9yZGluYXRlcyBhcyB3ZWxsLiBJZiB5b3UgYXJlIG5vYm9keSZyc3F1bztzIGJvc3MsIHRoZW4geW91IGhhdmUgbm8gc3Vib3JkaW5hdGVzLiBBcyBzaW1wbGUgYXMgdGhlc2UgcnVsZXMgYXJlLCBtYW55IHBlb3BsZSB3b3JraW5nIGZvciBUQUxMIGFyZSB1bnN1cmUgb2YgdG8gd2hvbSB0aGV5IHNob3VsZCBiZSB0dXJuaW5nIGluIHRoZWlyIHdlZWtseSBwcm9ncmVzcyByZXBvcnQgYW5kIGhvdyBtYW55IHN1Ym9yZGluYXRlcyB0aGV5IGhhdmUuIFdyaXRlIGEgcHJvZ3JhbSB0aGF0IHdpbGwgaGVscCBpbiBkZXRlcm1pbmluZyBmb3IgYW55IGVtcGxveWVlIHdobyB0aGUgaW1tZWRpYXRlIGJvc3Mgb2YgdGhhdCBlbXBsb3llZSBpcyBhbmQgaG93IG1hbnkgc3Vib3JkaW5hdGVzIHRoZXkgaGF2ZS4gUXVhbGl0eSBBc3N1cmFuY2UgYXQgVEFMTCBoYXZlIGRldmlzZWQgYSBzZXJpZXMgb2YgdGVzdHMgdG8gZW5zdXJlIHRoYXQgeW91ciBwcm9ncmFtIGlzIGNvcnJlY3QuIFRoZXNlIHRlc3QgYXJlIGRlc2NyaWJlZCBiZWxvdy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPk9uIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBpcyBhIHNpbmdsZSBwb3NpdGl2ZSBpbnRlZ2VyIG4sIHRlbGxpbmcgdGhlIG51bWJlciBvZiB0ZXN0IHNjZW5hcmlvcyB0byBmb2xsb3cuIEVhY2ggc2NlbmFyaW8gYmVnaW5zIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgdHdvIHBvc2l0aXZlIGludGVnZXJzIG0gYW5kIHEsIHdoZXJlIG0gKGF0IG1vc3QgMzAwMDApIGlzIHRoZSBudW1iZXIgb2YgZW1wbG95ZWVzIGFuZCBxIChhdCBtb3N0IDIwMCkgaXMgdGhlIG51bWJlciBvZiBxdWVyaWVzLiBUaGUgZm9sbG93aW5nIG0gbGluZXMgZWFjaCBsaXN0IGFuIGVtcGxveWVlIGJ5IHRocmVlIGludGVnZXJzIG9uIHRoZSBzYW1lIGxpbmU6IGVtcGxveWVlIElEIG51bWJlciAoc2l4IGRlY2ltYWwgZGlnaXRzLCB0aGUgZmlyc3Qgb25lIG9mIHdoaWNoIGlzIG5vdCB6ZXJvKSwgeWVhcmx5IHNhbGFyeSBpbiBFdXJvcyBhbmQgZmluYWxseSBoZWlnaHQgaW4gJm1pY3JvO20gKDEgJm1pY3JvO20gPSAxMC02IG1ldGVycyAmbmRhc2g7IGFjY3VyYWN5IGlzIGltcG9ydGFudCBhdCBUQUxMKS4gVGhlIGNoYWlycGVyc29uIGlzIHRoZSBlbXBsb3llZSB0aGF0IGVhcm5zIG1vcmUgdGhhbiBhbnlvbmUgZWxzZSBhbmQgaXMgYWxzbyB0aGUgdGFsbGVzdCBwZXJzb24gaW4gdGhlIGNvbXBhbnkuIFRoZW4gdGhlcmUgYXJlIHEgbGluZXMgbGlzdGluZyBxdWVyaWVzLiBFYWNoIHF1ZXJ5IGlzIGEgc2luZ2xlIGxlZ2FsIGVtcGxveWVlIElELjxcL3A+XHJcblxyXG48cD5UaGUgc2FsYXJ5IGlzIGEgcG9zaXRpdmUgaW50ZWdlciB3aGljaCBpcyBhdCBtb3N0IDEwIDAwMCAwMDAuIE5vIHR3byBlbXBsb3llZXMgaGF2ZSB0aGUgc2FtZSBJRCwgYW5kIG5vIHR3byBlbXBsb3llZXMgaGF2ZSB0aGUgc2FtZSBzYWxhcnkuIFRoZSBoZWlnaHQgb2YgYW4gZW1wbG95ZWUgaXMgYXQgbGVhc3QgMSAwMDAgMDAwICZtaWNybzttIGFuZCBhdCBtb3N0IDIgNTAwIDAwMCAmbWljcm87bS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBlbXBsb3llZSBJRCB4IGluIGEgcXVlcnkgb3V0cHV0IGEgc2luZ2xlIGxpbmUgd2l0aCB0d28gaW50ZWdlcnMgeSBrLCBzZXBhcmF0ZWQgYnkgb25lIHNwYWNlIGNoYXJhY3Rlciwgd2hlcmUgeSBpcyB0aGUgSUQgb2YgeCZyc3F1bztzIGJvc3MsIGFuZCBrIGlzIHRoZSBudW1iZXIgb2Ygc3Vib3JkaW5hdGVzIG9mIHguIElmIHRoZSBxdWVyeSBpcyB0aGUgSUQgb2YgdGhlIGNoYWlycGVyc29uLCB0aGVuIHlvdSBzaG91bGQgb3V0cHV0IDAgYXMgdGhlIElEIG9mIGhpcyBvciBoZXIgYm9zcyAoc2luY2UgdGhlIGNoYWlycGVyc29uIGhhcyBubyBpbW1lZGlhdGUgYm9zcyBleGNlcHQsIHBvc3NpYmx5LCBHb2QpLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d