가희와 영상 추천 시스템

가희는 YOTUBE에서 영상을 보고 있습니다. 가희가 R를 입력했을 때, 고유 번호가 id인 영상의 연관 지수는 아래와 같이 정의됩니다.

• 가희가 R를 입력하기 전 72시간 전부터 R를 입력할 때 까지

  • 고유 번호가 id인 영상을 본 횟수 v
  • 고유 번호가 id인 영상이 속한 카테고리를 C라 했을 때, 카테고리 C에 속하는 영상을 본 횟수 c

• 라고 했을 때, v와 c를 더한 값

YOTUBE에 있는 추천 영상은 아래 기준에 따라 순위가 결정됩니다.

1. 연관 지수가 높은 것
2. 연관 지수가 같다면, 영상 id가 작은 것부터

가희가 R를 입력할 때마다, 추천 영상 1위의 영상에 대한 정보를 출력해 주세요.

1번째 줄에 YOTUBE에 있는 영상 개수 N과 이벤트의 개수 E가 주어집니다.

그 다음 줄부터 N개의 줄에 VIDEO_NAME과 VIDEO_CATEGORY와 VIDEO_ID가 공백으로 구분되어 주어집니다. 이때

• 문자열 VIDEO_NAME은 공백, 숫자, 소문자로만 이루어져 있으며, 공백으로 시작하거나 끝나지 않습니다.
• 문자열 VIDEO_CATEGORY는 숫자, 소문자로만 이루어져 있습니다.
• VIDEO_ID는 1이상 109 이하의 정수입니다.

그 다음 줄부터 E개의 줄에 아래 형식 중 하나가 주어집니다.

• EVENT_TIME VIDEO_ID
  • EVENT_TIME에 가희는 고유 번호가 VIDEO_ID인 영상을 봅니다.
• EVENT_TIME R
  • EVENT_TIME에 가희는 추천 영상 1위의 영상 정보를 알고 싶어합니다.

이때, VIDEO_ID는 YOTUBE에 있는 영상 id만 주어집니다.

R 연산이 들어올 때마다, 추천 영상 1위의 동영상 id를 출력해 주세요.

• 1 ≤ E ≤ 5 × 105
• 1 ≤ N≤ 5 × 105
• 이벤트 E개가 일어난 시각은 모두 다르며, 먼저 일어난 순서대로 주어집니다.
• 주어지는 N개의 영상 id는 모두 다릅니다.
• R 연산이 일어나기 72시간 전부터 1초 전까지 본 영상이 최소 하나 이상 있습니다.
• VIDEO_CATEGORY의 길이는 15를 넘지 않고, VIDEO_NAME의 길이는 40을 넘지 않습니다.
• EVENT_TIME은 2000년 1월 1일 00:00:00 이후이며, 이 대회가 시작한 시각 이전입니다. 또한 EVENT_TIME은 YYYY-MM-DD hh:mm:ss 형식으로 주어집니다.
• R 연산은 최소 한 번 이상 들어옵니다.