시간 제한메모리 제한제출정답맞힌 사람정답 비율
1.5 초 1024 MB132492940.278%

문제

PVP 게임을 만들고 있는 도윤이는 매치메이킹 시스템을 구현하려고 합니다. 각 사람은 저마다 레이팅을 가지고 있고, 게임은 1:1 방식으로 이루어져 현재 매치메이킹 시스템에 있는 사람 중 레이팅 차이가 최소인 두 사람을 매칭하는 방식으로 이루어집니다. 도윤이를 대신해서 아래 쿼리 $Q$개를 처리하는 프로그램을 작성해봅시다.

  • $1$ $x$ $r$: 번호가 $x$, 레이팅이 $r$인 사람을 매치메이킹 시스템에 추가합니다. 이때 서로 다른 $1$번 쿼리에서 $x$의 값은 항상 서로 다르며, 번호와 레이팅은 모두 양의 정수입니다.
  • $2$: 레이팅 차가 최소인 정확히 한 쌍의 매칭을 만듭니다. 이런 쌍이 여럿이면 그중 아무 쌍이나 매칭해도 됩니다. 이 쿼리가 들어오면 매칭된 두 사람의 번호를 공백으로 구분해 출력하고, 두 사람을 매치메이킹 시스템에서 제거해야 합니다. 이때 매칭된 두 사람의 번호를 출력하는 순서는 무관합니다.

매치메이킹 시스템에 $2$명 이상이 남아 있을 때만 $2$번 쿼리가 주어지고, 전체 쿼리 중 적어도 하나 이상 $2$번 쿼리가 주어집니다.

입력

첫째 줄에 전체 쿼리의 수 $Q$가 주어집니다.

둘째 줄부터 $Q$개 줄에 걸쳐 쿼리가 주어집니다.

출력

$2$번 쿼리가 주어질 때마다 각 줄에 매칭된 두 사람의 번호를 공백으로 구분하여 출력합니다.

제한

  • $3\le Q\le 300\, 000$
  • $1\le x\le 300\, 000$
  • $1\le r\le 10^{9}$

서브태스크

번호배점제한
16

$Q \le 500$

211

$Q \le 10\,000$

358

모든 사람의 레이팅이 서로 다릅니다.

425

추가 제한 조건이 없습니다.

예제 입력 1

6
1 3 1
1 2 3
1 4 6
2
1 9 5
2

예제 출력 1

2 3
4 9

예제 입력 2

9
1 1 7
1 2 4
1 3 5
1 4 15
1 5 2
1 6 19
2
2
2

예제 출력 2

2 3
4 6
1 5

출처

School > 서울과학고등학교 > 2026 SciCom Qualification Test E번

채점 및 기타 정보

  • 예제는 채점하지 않는다.