30181번 - 조교의 기묘한 시험

문제

한 대학교 강의의 조교를 맡고 있는 실버는 눈치게임을 좋아합니다. 학생들이 실습에 즐겁게 참여할 수 있도록, 실버는 학생들의 실습 점수를 기묘하게 매기기로 했습니다.

각 학생은 자유롭게 실습에 들어오고 나갈 수 있지만, 한 번 실습에서 나가면 다시 들어올 수 없습니다. 실습에 들어올 때는, 종이에 1ドル$ 이상 1ドル,円 000,円 000$ 이하의 정수를 하나 적어서 들고 들어옵니다. 실습 도중 실버는 기묘한 이벤트를 엽니다. 기묘한 이벤트가 열리면, 현재 실습에 들어와 있는 학생들이 자신이 적은 정수를 바탕으로 다음과 같이 점수를 얻습니다.

• 자신이 적은 정수가 현재 실습에 있는 다른 사람과 겹친다면 점수를 얻지 못합니다.
• 자신이 적은 정수가 현재 실습에 있는 다른 사람과 겹치지 않는다면 1ドル$점을 얻습니다.
• 현재 실습에 있는 다른 사람과 겹치지 않게 정수를 적은 사람들 중 가장 큰 수를 적은 사람은 추가로 $s$점을 더 얻어 총 1ドル+s$점을 얻습니다. $s$는 이벤트마다 다를 수 있으며, 현재 실습에 있는 다른 사람과 겹치지 않게 정수를 적은 사람이 없다면 아무도 점수를 얻지 못합니다.

실버는 학생들의 실습 출입 기록과 기묘한 이벤트가 실시된 기록을 총 $Q$개의 질의로 정리했습니다. 질의의 형태는 다음 중 하나와 같습니다.

• 1ドル\ x$: 정수 $x$를 들고 있는 학생이 실습에 들어옵니다.
• 2ドル\ k$: 이전에 나간 사람을 포함, 지금까지 들어온 학생 중 $k$번째로 들어온 학생이 실습에서 나갑니다. $k$번째로 들어온 학생은 실습에 존재합니다.
• 3ドル\ s$: 기묘한 이벤트가 열립니다. 현재 실습에 들어와 있는 학생들 중 자신이 적은 정수가 현재 실습에 있는 다른 학생과 겹치지 않는 학생들이 1ドル$점을 얻습니다. 그 중 가장 큰 수를 적은 학생은 추가로 $s$점을 더 얻습니다.

모든 질의를 순서대로 처리한 후, 유형 1ドル$의 질의의 개수 $N$에 대해, 1ドル$번째부터 $N$번째로 들어온 학생이 받은 점수를 순서대로 출력하는 프로그램을 작성해봅시다.

입력

첫 번째 줄에 질의의 개수 $Q$가 주어집니다. (1ドル\le Q\le 500,円 000$)

다음 $Q$개의 줄에 질의가 주어집니다. 질의는 1ドル\ x,ドル 2ドル\ k,ドル 3ドル\ s$ 중 하나로 주어집니다.

• 유형 1ドル$의 질의의 개수는 1ドル$ 이상입니다.
• 유형 1ドル$의 질의에 대해, 1ドル\le x\le 1,円 000,円 000$이며 $x$는 정수입니다.
• 유형 2ドル$의 질의에 대해, 1ドル\le k$이며 $k$는 정수입니다.
• 유형 2ドル$의 질의에 대해, $k$번째로 들어온 학생은 실습에 존재합니다.
• 유형 3ドル$의 질의에 대해, 1ドル\le s\le 10^9$이며 $s$는 정수입니다.

출력

유형 1ドル$의 질의의 개수 $N$에 대해 $N$개의 줄을 출력합니다.

$i$번째 줄에는 $i$번째로 들어온 학생이 받은 점수를 출력합니다.

제한

힌트