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

문제

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

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

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

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

입력

첫째 줄에 두 정수 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+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWI0NTAgXHVjODE1XHVjMjE4IG4oJmxlOzMwLDAwMCksIG0oJmxlOzIwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBuXHVjNzQwIFx1YzBhY1x1YzZkMFx1Yzc1OCBcdWMyMThcdWFjZTAsIG1cdWM3NDAgXHVjNmIwXHViOWFjXHVhYzAwIFx1YzljMVx1YzE4ZCBcdWMwYzFcdWMwYWNcdWM2NDAgXHViZDgwXHVkNTU4XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWM1NGNcdWM1NDRcdWJjZjRcdWI4MjRcdWIyOTQgXHVjMGFjXHVjNmQwXHVjNzU4IFx1YzIxOFx1Yzc3NFx1YjJlNC4gXHViMmU0XHVjNzRjIG5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWMwYWNcdWM2ZDBcdWM3NTggXHVjODE1XHViY2Y0XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWMxMzggXHVjODE1XHVjMjE4IGEsIGIsIGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBhKGludCBcdWJjOTRcdWM3MDQpXHViMjk0IFx1YzBhY1x1YzZkMFx1Yzc1OCBJRCwgYigwJmxlO2ImbGU7MTAsMDAwLDAwMClcdWIyOTQgXHVhZTA5XHViOGNjLCBjKDEsMDAwLDAwMCZsZTtjJmxlOzIsNTAwLDAwMClcdWIyOTQgXHVhZGZjXHViYjM0XHVkNTVjIFx1YzJkY1x1YWMwNChcdWJkODQgXHViMmU4XHVjNzA0KVx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuIFx1YjJlNFx1Yzc0YyBtXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM5YzFcdWMxOGQgXHVjMGMxXHVjMGFjXHVjNjQwIFx1YmQ4MFx1ZDU1OFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjNTRjXHVjNTQ0XHViY2Y0XHViODI0XHViMjk0IFx1YzBhY1x1YzZkMFx1Yzc1OCBJRFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD4iLCJvdXRwdXQiOiI8cD5tXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWM3ODVcdWI4MjVcdWI0MWMgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1ZDU3NFx1YjJmOSBcdWMwYWNcdWM2ZDBcdWM3NTggXHVjOWMxXHVjMThkIFx1YzBjMVx1YzBhY1x1Yzc1OCBJRFx1YzY0MCBcdWJkODBcdWQ1NThcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgSURcdWFjMDAgXHVjMGFjXHVjN2E1XHVjNzdjIFx1YWNiZFx1YzZiMCwgXHVjOTg5IFx1YWMwMFx1YzdhNSBcdWM2MjRcdWI3OTggXHVhZGZjXHViYjM0XHVkNTU4XHVjNjAwXHVhY2UwIFx1YWMwMFx1YzdhNSBcdWI5Y2VcdWM3NDAgXHVhZTA5XHViOGNjXHViOTdjIFx1YmMxYlx1YjI5NCBcdWMwYWNcdWM2ZDBcdWM3NTggSURcdWM3N2MgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YzljMVx1YzE4ZCBcdWMwYzFcdWMwYWNcdWM3NTggSUQgXHViMzAwXHVjMmUwXHVjNWQwIDBcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0KFx1YzljMVx1YzE4ZCBcdWMwYzFcdWMwYWNcdWFjMDAgXHVjNWM2XHVjNzNjXHViYmMwXHViODVjKS48XC9wPiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjIzMTgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJXaG9cdTIwMTlzIHRoZSBib3NzPyIsImRlc2NyaXB0aW9uIjoiPHA+U2V2ZXJhbCBzdXJ2ZXlzIGluZGljYXRlIHRoYXQgdGhlIHRhbGxlciB5b3UgYXJlLCB0aGUgaGlnaGVyIHlvdSBjYW4gY2xpbWIgdGhlIGNvcnBvcmF0ZSBsYWRkZXIuIEF0IFRBTEwgRW50ZXJwcmlzZXMgSW5jLiB0aGlzICZsZHF1bztkZSBmYWN0byBzdGFuZGFyZCZyZHF1bzsgaGFzIGJlZW4gcHJvcGVybHkgZm9ybWFsaXplZDogeW91ciBib3NzIGlzIGFsd2F5cyBhdCBsZWFzdCBhcyB0YWxsIGFzIHlvdSBhcmUuIEZ1cnRoZXJtb3JlLCB5b3UgY2FuIHNhZmVseSBhc3N1bWUgdGhhdCB5b3VyIGJvc3MgZWFybnMgYSBiaXQgbW9yZSB0aGFuIHlvdSBkby4gSW4gZmFjdCwgeW91IGNhbiBiZSBhYnNvbHV0ZWx5IHN1cmUgdGhhdCB5b3VyIGltbWVkaWF0ZSBib3NzIGlzIHRoZSBwZXJzb24gd2hvIGVhcm5zIHRoZSBsZWFzdCBhbW9uZyBhbGwgdGhlIGVtcGxveWVlcyB0aGF0IGVhcm4gbW9yZSB0aGFuIHlvdSBhbmQgYXJlIGF0IGxlYXN0IGFzIHRhbGwgYXMgeW91IGFyZS4gRnVydGhlcm1vcmUsIGlmIHlvdSBhcmUgdGhlIGltbWVkaWF0ZSBib3NzIG9mIHNvbWVvbmUsIHRoYXQgcGVyc29uIGlzIHlvdXIgc3Vib3JkaW5hdGUsIGFuZCBhbGwgaGlzIHN1Ym9yZGluYXRlcyBhcmUgeW91ciBzdWJvcmRpbmF0ZXMgYXMgd2VsbC4gSWYgeW91IGFyZSBub2JvZHkmcnNxdW87cyBib3NzLCB0aGVuIHlvdSBoYXZlIG5vIHN1Ym9yZGluYXRlcy4gQXMgc2ltcGxlIGFzIHRoZXNlIHJ1bGVzIGFyZSwgbWFueSBwZW9wbGUgd29ya2luZyBmb3IgVEFMTCBhcmUgdW5zdXJlIG9mIHRvIHdob20gdGhleSBzaG91bGQgYmUgdHVybmluZyBpbiB0aGVpciB3ZWVrbHkgcHJvZ3Jlc3MgcmVwb3J0IGFuZCBob3cgbWFueSBzdWJvcmRpbmF0ZXMgdGhleSBoYXZlLiBXcml0ZSBhIHByb2dyYW0gdGhhdCB3aWxsIGhlbHAgaW4gZGV0ZXJtaW5pbmcgZm9yIGFueSBlbXBsb3llZSB3aG8gdGhlIGltbWVkaWF0ZSBib3NzIG9mIHRoYXQgZW1wbG95ZWUgaXMgYW5kIGhvdyBtYW55IHN1Ym9yZGluYXRlcyB0aGV5IGhhdmUuIFF1YWxpdHkgQXNzdXJhbmNlIGF0IFRBTEwgaGF2ZSBkZXZpc2VkIGEgc2VyaWVzIG9mIHRlc3RzIHRvIGVuc3VyZSB0aGF0IHlvdXIgcHJvZ3JhbSBpcyBjb3JyZWN0LiBUaGVzZSB0ZXN0IGFyZSBkZXNjcmliZWQgYmVsb3cuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5PbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgaXMgYSBzaW5nbGUgcG9zaXRpdmUgaW50ZWdlciBuLCB0ZWxsaW5nIHRoZSBudW1iZXIgb2YgdGVzdCBzY2VuYXJpb3MgdG8gZm9sbG93LiBFYWNoIHNjZW5hcmlvIGJlZ2lucyB3aXRoIGEgbGluZSBjb250YWluaW5nIHR3byBwb3NpdGl2ZSBpbnRlZ2VycyBtIGFuZCBxLCB3aGVyZSBtIChhdCBtb3N0IDMwMDAwKSBpcyB0aGUgbnVtYmVyIG9mIGVtcGxveWVlcyBhbmQgcSAoYXQgbW9zdCAyMDApIGlzIHRoZSBudW1iZXIgb2YgcXVlcmllcy4gVGhlIGZvbGxvd2luZyBtIGxpbmVzIGVhY2ggbGlzdCBhbiBlbXBsb3llZSBieSB0aHJlZSBpbnRlZ2VycyBvbiB0aGUgc2FtZSBsaW5lOiBlbXBsb3llZSBJRCBudW1iZXIgKHNpeCBkZWNpbWFsIGRpZ2l0cywgdGhlIGZpcnN0IG9uZSBvZiB3aGljaCBpcyBub3QgemVybyksIHllYXJseSBzYWxhcnkgaW4gRXVyb3MgYW5kIGZpbmFsbHkgaGVpZ2h0IGluICZtaWNybzttICgxICZtaWNybzttID0gMTAtNiBtZXRlcnMgJm5kYXNoOyBhY2N1cmFjeSBpcyBpbXBvcnRhbnQgYXQgVEFMTCkuIFRoZSBjaGFpcnBlcnNvbiBpcyB0aGUgZW1wbG95ZWUgdGhhdCBlYXJucyBtb3JlIHRoYW4gYW55b25lIGVsc2UgYW5kIGlzIGFsc28gdGhlIHRhbGxlc3QgcGVyc29uIGluIHRoZSBjb21wYW55LiBUaGVuIHRoZXJlIGFyZSBxIGxpbmVzIGxpc3RpbmcgcXVlcmllcy4gRWFjaCBxdWVyeSBpcyBhIHNpbmdsZSBsZWdhbCBlbXBsb3llZSBJRC48XC9wPlxyXG5cclxuPHA+VGhlIHNhbGFyeSBpcyBhIHBvc2l0aXZlIGludGVnZXIgd2hpY2ggaXMgYXQgbW9zdCAxMCAwMDAgMDAwLiBObyB0d28gZW1wbG95ZWVzIGhhdmUgdGhlIHNhbWUgSUQsIGFuZCBubyB0d28gZW1wbG95ZWVzIGhhdmUgdGhlIHNhbWUgc2FsYXJ5LiBUaGUgaGVpZ2h0IG9mIGFuIGVtcGxveWVlIGlzIGF0IGxlYXN0IDEgMDAwIDAwMCAmbWljcm87bSBhbmQgYXQgbW9zdCAyIDUwMCAwMDAgJm1pY3JvO20uPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggZW1wbG95ZWUgSUQgeCBpbiBhIHF1ZXJ5IG91dHB1dCBhIHNpbmdsZSBsaW5lIHdpdGggdHdvIGludGVnZXJzIHkgaywgc2VwYXJhdGVkIGJ5IG9uZSBzcGFjZSBjaGFyYWN0ZXIsIHdoZXJlIHkgaXMgdGhlIElEIG9mIHgmcnNxdW87cyBib3NzLCBhbmQgayBpcyB0aGUgbnVtYmVyIG9mIHN1Ym9yZGluYXRlcyBvZiB4LiBJZiB0aGUgcXVlcnkgaXMgdGhlIElEIG9mIHRoZSBjaGFpcnBlcnNvbiwgdGhlbiB5b3Ugc2hvdWxkIG91dHB1dCAwIGFzIHRoZSBJRCBvZiBoaXMgb3IgaGVyIGJvc3MgKHNpbmNlIHRoZSBjaGFpcnBlcnNvbiBoYXMgbm8gaW1tZWRpYXRlIGJvc3MgZXhjZXB0LCBwb3NzaWJseSwgR29kKS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=