가장 오래 빌린 회원

문제

어느 도서관의 대출 기록 시스템은 하루 동안 쌓인 로그를 시간순으로 한 줄씩 남긴다. 각 줄은 사건이 일어난 시각 t(하루 시작부터 지난 초), 사건 종류 k, 회원 번호 u, 책 번호 b로 이루어진다. k가 1이면 회원 u가 책 b를 빌린 것이고, k가 2이면 회원 u가 책 b를 반납한 것이다. 로그는 시각이 줄어들지 않는 순서로 주어지며, 같은 시각의 사건은 주어진 순서대로 일어난 것으로 본다. 로그는 항상 올바르다. 즉 빌리는 책은 그 순간 누구에게도 빌려진 상태가 아니고, 반납하는 책은 그 줄의 회원 u가 빌려 간 상태이다. 첫 번째 사건은 항상 대출이다. 한 책이 여러 번 빌려지고 반납될 수 있다. 회원이 책을 빌린 시각부터 그 책을 반납한 시각까지의 시간(초)을 그 대출의 대출 시간이라 하자. 로그가 끝날 때까지 반납되지 않은 책은 마감 시각 T에 반납된 것으로 계산한다. 한 회원이 여러 권을 동시에 빌릴 수 있으며, 대출 시간은 책마다 따로 계산하여 모두 더한다. 대출을 한 번 이상 한 회원 중에서 대출 시간의 합이 가장 큰 회원을 찾아, 회원 번호와 그 합을 출력하는 프로그램을 작성하라. 합이 같은 회원이 여럿이면 번호가 가장 작은 회원을 고른다.

입력

첫 줄에 로그 줄 수 N과 마감 시각 T가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 200000, 0 ≤ T ≤ 10^9) 다음 N개의 줄에 각각 정수 t, k, u, b가 공백으로 구분되어 주어진다. (0 ≤ t ≤ T, k는 1 또는 2, 1 ≤ u, b ≤ 10^9) t는 줄이 내려갈수록 줄어들지 않는다.

출력

첫 줄에 회원 번호와 그 회원의 대출 시간 합을 공백으로 구분하여 출력한다.

5 100
10 1 7 100
20 1 3 200
30 2 7 100
50 2 3 200
60 1 3 100

3 70

2 10
0 1 5 1
0 1 2 2

2 10

출처: Devin.KR 자체 제작