시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB75282336.508%

문제

성관이는 시간 여행을 할 수 있는 타임머신을 개발했다! 하지만, 이 문제는 알고리즘 문제이기 때문에, 그는 무엇인가 멋진 일을 하는 대신 multiset에 시간 여행을 적용하기로 했다.

시간 여행이 포함된 multiset은, 다음과 같은 기능을 제공한다.

  1. 특정 시간 t로 가서, multiset에 정수 x를 추가한다.
  2. 특정 시간 t로 가서, multiset에서 정수 x를 제거한다. (시간 t에 multiset에 정수 x가 존재함은 보장된다.)
  3. 특정 시간 t에 multiset에 정수 x가 몇 개 존재하는지 출력한다.

예를 들어 설명해보자. 정수 1이 시간 2에 두 개 추가되고, 시간 5에 하나 제거되었다고 하자. 이때, 정수 1은 시간 2~4 동안은 2개, 시간 5~에는 1개가 존재한다. 만약 시간 4에서 정수 1을 하나 제거하였다면, 이제 정수 1은 시간 2~3 동안 2개, 시간 4동안 1개, 시간 5~에는 존재하지 않는다. 이 상황에서, 시간 5에서 정수 1을 하나 제거하는 연산은, 정수 1이 그 시점에 존재하지 않으므로 조건에 맞지 않는 연산이다. (따라서 입력으로 들어오지 않는다.)

위와 같은 동작을 구현하는 프로그램을 작성하시오.

입력

입력의 첫 번째 줄에는 질의의 개수 N이 주어진다. (1 ≤ N ≤ 100,000)

다음 N개의 줄에는 질의의 정보가 주어진다. 각 질의는 세 개의 자연수 ai, ti, xi를 갖는다. (1 ≤ ai ≤ 3, 1 ≤ ti, xi ≤ 109) ai는 질의의 종류를 의미한다. ti, xi는 본문의 질의 설명에 나타나는 변수이다.

출력

ai가 3인 질의가 주어질 때마다, 그 질의의 결과를 출력한다.

예제 입력 1

6
1 1 5
3 5 5
1 2 5
3 6 5
2 3 5
3 7 5

예제 출력 1

1
2
1

예제 입력 2

3
1 1 1
2 2 1
3 3 1

예제 출력 2

0

출처

  • 문제의 오타를 찾은 사람: cheetose