문제 추천 시스템 Version 2

면접 대비

시간 제한1초메모리 제한512 MB

요약

문제 목록에 추가와 삭제를 지원하면서, 분류별, 전체, 또는 난이도 기준 이상과 이하에서 가장 어렵거나 쉬운 문제 번호를 출력하는 시스템을 구현한다.

난이도: 보통10점 중 6점
유형: 구현, 해시맵, 정렬, 이분 탐색
정답자: 아직 제출이 없습니다

문제

tony9402는 최근 깃헙에 코딩테스트 대비 문제를 직접 뽑아서 "문제 번호, 난이도, 알고리즘 분류"로 정리해놨다.

깃헙을 이용하여 공부하시는 분들을 위해 새로운 기능을 추가해보려고 한다.

만들려고 하는 명령어는 총 3가지가 있다. 아래 표는 각 명령어에 대한 설명이다.


recommend $G$ $x$	$x$ 가 1인 경우 추천 문제 리스트에서 알고리즘 분류가 $G$ 인 문제 중 가장 어려운 문제 번호를 출력한다. 조건을 만족하는 문제가 여러 개라면 그 중 문제 번호가 큰 것으로 출력한다. $x$ 가 -1인 경우 추천 문제 리스트에서 알고리즘 분류가 $G$ 인 문제 중 가장 쉬운 문제 번호를 출력한다. 조건을 만족하는 문제가 여러 개라면 그 중 문제 번호가 작은 것으로 출력한다. 해당 명령어는 해당 그룹 $G$ 에 문제 번호가 한 개 이상이 있을 경우에만 주어진다.
recommend2 $x$	$x$ 가 1인 경우 추천 문제 리스트에서 알고리즘 분류 상관없이 가장 어려운 문제 번호를 출력한다. 조건을 만족하는 문제가 여러 개라면 그 중 문제 번호가 큰 것으로 출력한다. $x$ 가 -1인 경우 추천 문제 리스트에서 알고리즘 분류 상관없이 가장 쉬운 문제 번호를 출력한다. 조건을 만족하는 문제가 여러 개라면 그 중 문제 번호가 작은 것으로 출력한다.
recommend3 $x$ $L$	$x$ 가 1인 경우 추천 문제 리스트에서 알고리즘 분류 상관없이 난이도 $L$ 보다 크거나 같은 문제 중 가장 쉬운 문제 번호를 출력한다. 조건을 만족하는 문제가 여러 개라면 그 중 문제 번호가 작은 것으로 출력한다. 만약 조건을 만족하는 문제 번호가 없다면 -1을 출력한다. $x$ 가 -1인 경우 추천 문제 리스트에서 알고리즘 분류 상관없이 난이도 $L$ 보다 작은 문제 중 가장 어려운 문제 번호를 출력한다. 조건을 만족하는 문제가 여러 개라면 그 중 문제 번호가 큰 것으로 출력한다. 만약 조건을 만족하는 문제 번호가 없다면 -1을 출력한다.
add $P$ $L$ $G$	추천 문제 리스트에 난이도가 $L$ 이고 알고리즘 분류가 $G$ 인 문제 번호 $P$ 를 추가한다. (추천 문제 리스트에 없는 문제 번호 $P$ 만 입력으로 주어진다. 이전에 추천 문제 리스트에 있던 문제 번호가 다른 난이도와 다른 알고리즘 분류로 다시 들어 올 수 있다.)
solved $P$	추천 문제 리스트에서 문제 번호 $P$ 를 제거한다. (추천 문제 리스트에 있는 문제 번호 $P$ 만 입력으로 주어진다.)

명령어 recommend, recommend2, recommend3는 추천 문제 리스트에 문제가 하나 이상 있을 때만 주어진다.

명령어 solved는 추천 문제 리스트에 문제 번호가 하나 이상 있을 때만 주어진다.

위 명령어들을 수행하는 추천 시스템을 만들어보자.

입력

첫 번째 줄에 추천 문제 리스트에 있는 문제의 개수 $N$ 가 주어진다.

두 번째 줄부터 $N + 1$ 줄까지 문제 번호 $P$ 와 난이도 $L$ , 알고리즘 분류 $G$ 가 공백으로 구분되어 주어진다.

$N + 2$ 줄은 입력될 명령문의 개수 $M$ 이 주어진다.

그 다음줄부터 $M$ 개의 위에서 설명한 명령문이 입력된다.

출력

recommend, recommend2, recommend3 명령이 주어질 때마다 문제 번호를 한 줄씩 출력한다. 주어지는 recommend, recommend2, recommend3 명령어의 총 개수는 최소 1개 이상이다.

제한

$1 \le N, P \le 100,000$
$1 \le M \le 10,000$
$1 \le L, G \le 100$ , $L$ 와 $G$ 은 자연수
$x = \pm 1$

예제2

예제 1

입력

5
1000 1 1
1001 2 1
19998 78 2
2667 37 3
2042 55 3
12
add 1402 59 1
recommend 1 1
recommend2 1
recommend3 1 50
recommend3 -1 50
solved 1000
solved 2667
recommend 2 1
recommend 1 -1
recommend2 -1
solved 1001
recommend 1 -1

예상 출력

예제 2

입력

3
19998 78 2
2667 37 3
2042 55 3
6
recommend3 -1 50
solved 2667
recommend3 -1 50
recommend3 1 70
solved 19998
recommend3 1 70

예상 출력