시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 166 52 29 36.709%

문제

비어있는 배열 A가 주어졌을 때, 다음과 같은 5가지 쿼리를 수행하는 프로그램을 작성하시오. 배열의 인덱스는 1부터 시작한다.

  • 1 x: 배열 A의 끝에 x를 추가한다.
  • 2 L R x: A의 L번째 수부터 R번째 수까지 중에서 x와 xor한 값이 가장 큰 y를 찾아 출력한다.
  • 3 k: 배열 A의 마지막 k개를 제거한다.
  • 4 L R x: A의 L번째 수부터 R번째 수까지 중에서 x보다 작거나 같은 원소의 개수를 출력한다.
  • 5 L R k: A의 L번째 수부터 R번째 수까지 중에서 k번째로 작은 수를 출력한다.

입력

첫째 줄에 쿼리의 개수 M (1 ≤ M ≤ 500,000)이 주어진다.

둘째 줄부터 M개의 줄에는 쿼리가 한 줄에 하나씩 주어진다. (1 ≤ x ≤ 500,000, 1 ≤ L ≤ R ≤ N)

3번 쿼리의 경우 1 ≤ k ≤ N, 5번 쿼리의 경우: k ≤ R-L+1

출력

2,4,5번 쿼리의 정답을 한 줄에 하나씩 순서대로 출력한다.

예제 입력

10
1 8
5 1 1 1
1 2
2 2 2 7
2 2 2 7
1 1
4 2 2 2
2 1 2 3
4 1 3 5
1 6

예제 출력

8
2
2
1
8
2

예제 입력 2

16
1 1
1 2
2 1 1 1
2 2 2 1
2 1 2 3
4 1 1 1
4 2 2 1
4 1 2 3
5 1 1 1
5 2 2 1
5 1 2 2
3 1
3 1
1 1
1 2
3 2

예제 출력 2

1
2
1
1
0
2
1
2
2

힌트

출처