시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 64 13 10 25.000%

문제

mex는 어떤 수열에 포함되지 않은 수 중에서 가장 작은 자연수를 찾는 함수이다. 예를 들어, mex([1,2,3]) = 4, mex([5,3,1,1,4]) = 2, mex([1,5,2,1,5,2,1,2]) = 3이다.

비어있는 배열 A와 쿼리 N개가 주어졌을 때, 쿼리를 수행해보자. 쿼리는 총 3가지가 있으며, 아래와 같다.

  • 1 l r: 구간 [l, r]에 속하는 모든 자연수를 배열 A에 추가한다. 배열에 이미 있는 자연수는 또 추가하지 않는다.
  • 2 l r: 구간 [l, r]에 속하는 모든 자연수를 배열 A에서 제거한다.
  • 3 l r: 구간 [l, r]에 속하는 모든 자연수 x에 대해서, 다음을 수행한다.
    • x가 배열 A에 있으면, 배열에서 제거한다.
    • x가 배열 A에 없으면, 배열에 추가한다.

각 쿼리를 수행한 다음에 mex(A)를 구해보자.

입력

첫째 줄에 쿼리의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 쿼리를 나타내는 q, l, r (1 ≤ q ≤ 3, 1 ≤ l ≤ r ≤ 1018)이 주어진다.

출력

각각의 쿼리를 수행한 후에 mex(A)를 출력한다.

예제 입력 1

3
1 3 4
3 1 6
2 1 3

예제 출력 1

1
3
1

예제 입력 2

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

예제 출력 2

4
4
4
1

출처