인원 감축

많은 IT 기업이 자사가 "과잉 채용" 상태였다는 것을 깨달았다. 장부를 보니 일부 직원을 해고해야 할 수도 있다. 회사는 이익을 지키려고 그 시점에 연봉이 가장 높은 직원을 항상 해고한다. 최고 연봉이 같은 직원이 여럿이면 이름이 사전순으로 앞서는 직원을 해고한다.

사기를 유지하려고 승급도 이루어지므로, 누구를 해고할지 정하기는 더 까다로워진다.

직원들의 초기 연봉이 주어지고, 그 뒤에 행동의 순서가 이어진다. 행동은 직원을 해고하거나 재직 중인 직원에게 승급을 주는 것이다. 해고가 일어날 때마다 어떤 직원이 해고되는지 구하라.

첫째 줄에 직원 수 $n$ ($1 \le n \le 10^5$)과 행동 수 $a$ ($1 \le a \le 2 \times 10^5$)이 주어진다.

다음 $n$ 줄에는 직원 이름 $e$와 연봉 $s$ ($1 \le s \le 10^9$)가 주어진다. 이름은 서로 다르며 영어 소문자 1자 이상 20자 이하로 이루어진다.

다음 $a$ 줄은 행동을 나타낸다. 줄의 첫 정수가 1이면 승급이며, 이어서 직원 이름 $e$와 승급액 $r$ ($1 \le r \le 10^9$)이 주어진다. 승급을 받는 직원은 처음 목록에 있었고 아직 해고되지 않은 직원이다. 줄의 첫 정수가 2이면 현재 연봉이 가장 높은 직원을 해고한다. 같은 연봉이면 이름이 사전순으로 앞서는 직원을 해고한다. 2로 시작하는 줄은 최대 $n$번 나타난다.

해고가 일어날 때마다 해고된 직원의 이름과 해고 시점의 연봉을 공백으로 구분하여 한 줄에 출력한다.