시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB454450.000%

문제

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

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

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

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

입력

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

다음 m개의 줄에는 직속 상사와 부하의 수를 알아보려는 사원의 ID가 주어진다. 사원의 정보로 주어진 사원의 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

예제 입력 2

4 4
200002 12234 1832001
200003 15002 1745201
200004 18745 1883410
200001 24834 1921313
200004
200002
200003
200001

예제 출력 2

200001 2
200004 0
200004 0
0 3
W3sicHJvYmxlbV9pZCI6IjIzMTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYzFcdWMwYWMgXHVjYzNlXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM4ZmNcdWMyZGRcdWQ2OGNcdWMwYWMgXHVjNmQ0XHViNGRjXHVjNWQwXHVjMTFjXHViMjk0IFx1YzYyNFx1YjdhYlx1YjNkOVx1YzU0OCBcdWM1ZjRcdWMyZWNcdWQ3ODggXHVjNzdjXHVjNzQ0IFx1ZDU1OFx1YmE3NCBcdWFkZjhcdWM1ZDAgXHViNTMwXHViNzdjIFx1YzJiOVx1YzljNFx1ZDU2MCBcdWMyMThcdWIzYzQgXHVjNzg4XHVhY2UwLCBcdWFkZjhcdWI5Y2NcdWQwN2MgXHViOWNlXHVjNzQwIFx1YWUwOVx1YjhjY1x1Yjk3YyBcdWJjMWJcdWM3NDQgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjOTg5LCBcdWM1YjRcdWI1YTQgXHVjMGFjXHVjNmQwXHVjNzU4IFx1YzBjMVx1YzBhY1x1YjI5NCBcdWM4MDFcdWM1YjRcdWIzYzQgXHVhZGY4IFx1YzBhY1x1YzZkMFx1YjljY1x1ZDA3Y1x1Yzc0MCBcdWQ2OGNcdWMwYWNcdWM1ZDBcdWMxMWMgXHVhZGZjXHViYjM0XHVkNTVjIFx1YWM4M1x1Yzc3NFx1YWNlMCwgXHVhZGY4IFx1YzBhY1x1YzZkMFx1YmNmNFx1YjJlNCBcdWI5Y2VcdWM3NDAgXHVhZTA5XHViOGNjXHViOTdjIFx1YmMxYlx1YjI5NFx1YjJlNC4gXHViNjEwLCBcdWM1YjRcdWIyOTAgXHVjMGFjXHVjNmQwXHVjNzU4IFx1YzljMVx1YzE4ZCBcdWMwYzFcdWMwYWNcdWIyOTQsIFx1YzgwMVx1YzViNFx1YjNjNCBcdWFkZjggXHVjMGFjXHVjNmQwXHViOWNjXHVkMDdjIFx1ZDY4Y1x1YzBhY1x1YzVkMFx1YzExYyBcdWFkZmNcdWJiMzRcdWQ1ODhcdWFjZTAsIFx1YWRmOCBcdWMwYWNcdWM2ZDBcdWJjZjRcdWIyZTQgXHViOWNlXHVjNzQwIFx1YWUwOVx1YjhjY1x1Yjk3YyBcdWJjMWJcdWIyOTQgXHVjMGFjXHViNzhjXHViNGU0IFx1YzkxMVx1YzVkMFx1YzExYyBcdWFjMDBcdWM3YTUgXHVjODAxXHVjNzQwIFx1YWUwOVx1YjhjY1x1Yjk3YyBcdWJjMWJcdWIyOTQgXHVjMGFjXHViNzhjXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1YjRcdWIyOTAgXHVjMGFjXHVjNmQwXHVjNzU4IFx1YzljMVx1YzE4ZCBcdWMwYzFcdWMwYWNcdWM1ZDBcdWFjOGMgXHVjNzg4XHVjNWI0XHVjMTFjLCBcdWFkZjggXHVjMGFjXHVjNmQwXHVjNzQwIFx1YmQ4MFx1ZDU1OFx1YWMwMCBcdWI0MWNcdWIyZTQuIFx1YzViNFx1YjVhNCBcdWMwYWNcdWM2ZDBcdWM3NTggXHViZDgwXHVkNTU4XHVjNzU4IFx1YmQ4MFx1ZDU1OFx1YjRlNFx1YjNjNCBcdWJhYThcdWI0NTAgXHVhZGY4IFx1YzBhY1x1YzZkMFx1Yzc1OCBcdWJkODBcdWQ1NThcdWI3N2MgXHVkNTU4XHVjNzkwLiBcdWI5Y2NcdWM1N2RcdWM1ZDAgXHVjNWI0XHViMjkwIFx1YzBhY1x1YzZkMFx1Yzc3NCBcdWIyMDRcdWFkNmNcdWM3NTggXHVjMGMxXHVjMGFjXHViM2M0IFx1YzU0NFx1YjJjOFx1YmE3NCBcdWFkZjggXHVjMGFjXHVjNmQwXHVjNzQwIFx1YmQ4MFx1ZDU1OFx1YWMwMCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzhmY1x1YzJkZFx1ZDY4Y1x1YzBhYyBcdWM2ZDRcdWI0ZGNcdWM3NTggXHVjMGMxXHVjMGFjLVx1YmQ4MFx1ZDU1OCBcdWFkMDBcdWFjYzRcdWFjMDAgXHVjNzA0XHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWM4MTVcdWM3NThcdWI0MjAgXHViNTRjLCBcdWJhODdcdWJhODcgXHVjMGFjXHVjNmQwXHVjNzU4IFx1YzljMVx1YzE4ZCBcdWMwYzFcdWMwYWNcdWM2NDAgXHViZDgwXHVkNTU4XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViNDUwIFx1YzgxNVx1YzIxOCBuKDEgJmxlOyBuICZsZTsgMzAsMDAwKSwgbSgxICZsZTsgbSAmbGU7IDIwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBuXHVjNzQwIFx1YzBhY1x1YzZkMFx1Yzc1OCBcdWMyMThcdWFjZTAsIG1cdWM3NDAgXHVjNmIwXHViOWFjXHVhYzAwIFx1YzljMVx1YzE4ZCBcdWMwYzFcdWMwYWNcdWM2NDAgXHViZDgwXHVkNTU4XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWM1NGNcdWM1NDRcdWJjZjRcdWI4MjRcdWIyOTQgXHVjMGFjXHVjNmQwXHVjNzU4IFx1YzIxOFx1Yzc3NFx1YjJlNC4gXHViMmU0XHVjNzRjIG5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWMwYWNcdWM2ZDBcdWM3NTggXHVjODE1XHViY2Y0XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWMxMzggXHVjODE1XHVjMjE4IGEsIGIsIGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBhKDEgJmxlOyBhICZsZTsgMiwxNDcsNDgzLDY0NylcdWIyOTQgXHVjMGFjXHVjNmQwXHVjNzU4IElELCBiKDAgJmxlOyBiICZsZTsgMTAsMDAwLDAwMClcdWIyOTQgXHVhZTA5XHViOGNjLCBjKDEsMDAwLDAwMCAmbGU7IGMgJmxlOyAyLDUwMCwwMDApXHViMjk0IFx1YWRmY1x1YmIzNFx1ZDU1YyBcdWMyZGNcdWFjMDQoXHViZDg0IFx1YjJlOFx1YzcwNClcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWMwYWNcdWM2ZDBcdWM3NTggSURcdWIyOTQgXHVjOTExXHViY2Y1XHViNDE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIG1cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzljMVx1YzE4ZCBcdWMwYzFcdWMwYWNcdWM2NDAgXHViZDgwXHVkNTU4XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWM1NGNcdWM1NDRcdWJjZjRcdWI4MjRcdWIyOTQgXHVjMGFjXHVjNmQwXHVjNzU4IElEXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjMGFjXHVjNmQwXHVjNzU4IFx1YzgxNVx1YmNmNFx1Yjg1YyZuYnNwO1x1YzhmY1x1YzViNFx1YzljNCBcdWMwYWNcdWM2ZDBcdWM3NTggSURcdWI5Y2MgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPm1cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1Yzc4NVx1YjgyNVx1YjQxYyBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVkNTc0XHViMmY5IFx1YzBhY1x1YzZkMFx1Yzc1OCBcdWM5YzFcdWMxOGQgXHVjMGMxXHVjMGFjXHVjNzU4IElEXHVjNjQwIFx1YmQ4MFx1ZDU1OFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBJRFx1YWMwMCBcdWMwYWNcdWM3YTVcdWM3N2MgXHVhY2JkXHVjNmIwLCBcdWM5ODkgXHVhYzAwXHVjN2E1IFx1YzYyNFx1Yjc5OCBcdWFkZmNcdWJiMzRcdWQ1NThcdWM2MDBcdWFjZTAgXHVhYzAwXHVjN2E1IFx1YjljZVx1Yzc0MCBcdWFlMDlcdWI4Y2NcdWI5N2MgXHViYzFiXHViMjk0IFx1YzBhY1x1YzZkMFx1Yzc1OCBJRFx1Yzc3YyBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVjOWMxXHVjMThkIFx1YzBjMVx1YzBhY1x1Yzc1OCBJRCBcdWIzMDBcdWMyZTBcdWM1ZDAgMFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjMxOCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ildob1x1MjAxOXMgdGhlIGJvc3M/IiwiZGVzY3JpcHRpb24iOiI8cD5TZXZlcmFsIHN1cnZleXMgaW5kaWNhdGUgdGhhdCB0aGUgdGFsbGVyIHlvdSBhcmUsIHRoZSBoaWdoZXIgeW91IGNhbiBjbGltYiB0aGUgY29ycG9yYXRlIGxhZGRlci4gQXQgVEFMTCBFbnRlcnByaXNlcyBJbmMuIHRoaXMgJmxkcXVvO2RlIGZhY3RvIHN0YW5kYXJkJnJkcXVvOyBoYXMgYmVlbiBwcm9wZXJseSBmb3JtYWxpemVkOiB5b3VyIGJvc3MgaXMgYWx3YXlzIGF0IGxlYXN0IGFzIHRhbGwgYXMgeW91IGFyZS4gRnVydGhlcm1vcmUsIHlvdSBjYW4gc2FmZWx5IGFzc3VtZSB0aGF0IHlvdXIgYm9zcyBlYXJucyBhIGJpdCBtb3JlIHRoYW4geW91IGRvLiBJbiBmYWN0LCB5b3UgY2FuIGJlIGFic29sdXRlbHkgc3VyZSB0aGF0IHlvdXIgaW1tZWRpYXRlIGJvc3MgaXMgdGhlIHBlcnNvbiB3aG8gZWFybnMgdGhlIGxlYXN0IGFtb25nIGFsbCB0aGUgZW1wbG95ZWVzIHRoYXQgZWFybiBtb3JlIHRoYW4geW91IGFuZCBhcmUgYXQgbGVhc3QgYXMgdGFsbCBhcyB5b3UgYXJlLiBGdXJ0aGVybW9yZSwgaWYgeW91IGFyZSB0aGUgaW1tZWRpYXRlIGJvc3Mgb2Ygc29tZW9uZSwgdGhhdCBwZXJzb24gaXMgeW91ciBzdWJvcmRpbmF0ZSwgYW5kIGFsbCBoaXMgc3Vib3JkaW5hdGVzIGFyZSB5b3VyIHN1Ym9yZGluYXRlcyBhcyB3ZWxsLiBJZiB5b3UgYXJlIG5vYm9keSZyc3F1bztzIGJvc3MsIHRoZW4geW91IGhhdmUgbm8gc3Vib3JkaW5hdGVzLiBBcyBzaW1wbGUgYXMgdGhlc2UgcnVsZXMgYXJlLCBtYW55IHBlb3BsZSB3b3JraW5nIGZvciBUQUxMIGFyZSB1bnN1cmUgb2YgdG8gd2hvbSB0aGV5IHNob3VsZCBiZSB0dXJuaW5nIGluIHRoZWlyIHdlZWtseSBwcm9ncmVzcyByZXBvcnQgYW5kIGhvdyBtYW55IHN1Ym9yZGluYXRlcyB0aGV5IGhhdmUuIFdyaXRlIGEgcHJvZ3JhbSB0aGF0IHdpbGwgaGVscCBpbiBkZXRlcm1pbmluZyBmb3IgYW55IGVtcGxveWVlIHdobyB0aGUgaW1tZWRpYXRlIGJvc3Mgb2YgdGhhdCBlbXBsb3llZSBpcyBhbmQgaG93IG1hbnkgc3Vib3JkaW5hdGVzIHRoZXkgaGF2ZS4gUXVhbGl0eSBBc3N1cmFuY2UgYXQgVEFMTCBoYXZlIGRldmlzZWQgYSBzZXJpZXMgb2YgdGVzdHMgdG8gZW5zdXJlIHRoYXQgeW91ciBwcm9ncmFtIGlzIGNvcnJlY3QuIFRoZXNlIHRlc3QgYXJlIGRlc2NyaWJlZCBiZWxvdy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPk9uIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBpcyBhIHNpbmdsZSBwb3NpdGl2ZSBpbnRlZ2VyIG4sIHRlbGxpbmcgdGhlIG51bWJlciBvZiB0ZXN0IHNjZW5hcmlvcyB0byBmb2xsb3cuIEVhY2ggc2NlbmFyaW8gYmVnaW5zIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgdHdvIHBvc2l0aXZlIGludGVnZXJzIG0gYW5kIHEsIHdoZXJlIG0gKGF0IG1vc3QgMzAwMDApIGlzIHRoZSBudW1iZXIgb2YgZW1wbG95ZWVzIGFuZCBxIChhdCBtb3N0IDIwMCkgaXMgdGhlIG51bWJlciBvZiBxdWVyaWVzLiBUaGUgZm9sbG93aW5nIG0gbGluZXMgZWFjaCBsaXN0IGFuIGVtcGxveWVlIGJ5IHRocmVlIGludGVnZXJzIG9uIHRoZSBzYW1lIGxpbmU6IGVtcGxveWVlIElEIG51bWJlciAoc2l4IGRlY2ltYWwgZGlnaXRzLCB0aGUgZmlyc3Qgb25lIG9mIHdoaWNoIGlzIG5vdCB6ZXJvKSwgeWVhcmx5IHNhbGFyeSBpbiBFdXJvcyBhbmQgZmluYWxseSBoZWlnaHQgaW4gJm1pY3JvO20gKDEgJm1pY3JvO20gPSAxMC02IG1ldGVycyAmbmRhc2g7IGFjY3VyYWN5IGlzIGltcG9ydGFudCBhdCBUQUxMKS4gVGhlIGNoYWlycGVyc29uIGlzIHRoZSBlbXBsb3llZSB0aGF0IGVhcm5zIG1vcmUgdGhhbiBhbnlvbmUgZWxzZSBhbmQgaXMgYWxzbyB0aGUgdGFsbGVzdCBwZXJzb24gaW4gdGhlIGNvbXBhbnkuIFRoZW4gdGhlcmUgYXJlIHEgbGluZXMgbGlzdGluZyBxdWVyaWVzLiBFYWNoIHF1ZXJ5IGlzIGEgc2luZ2xlIGxlZ2FsIGVtcGxveWVlIElELjxcL3A+XHJcblxyXG48cD5UaGUgc2FsYXJ5IGlzIGEgcG9zaXRpdmUgaW50ZWdlciB3aGljaCBpcyBhdCBtb3N0IDEwIDAwMCAwMDAuIE5vIHR3byBlbXBsb3llZXMgaGF2ZSB0aGUgc2FtZSBJRCwgYW5kIG5vIHR3byBlbXBsb3llZXMgaGF2ZSB0aGUgc2FtZSBzYWxhcnkuIFRoZSBoZWlnaHQgb2YgYW4gZW1wbG95ZWUgaXMgYXQgbGVhc3QgMSAwMDAgMDAwICZtaWNybzttIGFuZCBhdCBtb3N0IDIgNTAwIDAwMCAmbWljcm87bS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBlbXBsb3llZSBJRCB4IGluIGEgcXVlcnkgb3V0cHV0IGEgc2luZ2xlIGxpbmUgd2l0aCB0d28gaW50ZWdlcnMgeSBrLCBzZXBhcmF0ZWQgYnkgb25lIHNwYWNlIGNoYXJhY3Rlciwgd2hlcmUgeSBpcyB0aGUgSUQgb2YgeCZyc3F1bztzIGJvc3MsIGFuZCBrIGlzIHRoZSBudW1iZXIgb2Ygc3Vib3JkaW5hdGVzIG9mIHguIElmIHRoZSBxdWVyeSBpcyB0aGUgSUQgb2YgdGhlIGNoYWlycGVyc29uLCB0aGVuIHlvdSBzaG91bGQgb3V0cHV0IDAgYXMgdGhlIElEIG9mIGhpcyBvciBoZXIgYm9zcyAoc2luY2UgdGhlIGNoYWlycGVyc29uIGhhcyBubyBpbW1lZGlhdGUgYm9zcyBleGNlcHQsIHBvc3NpYmx5LCBHb2QpLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=