문제
길이가 N인 배열 A1, A2, ..., AN이 있다.
위 쿼리를 빠르게 수행하는 프로그램을 작성하여라.
먼저 아래 형식의 쿼리를 M번 수행한다.
a b v : Ai에 v를 삽입한다. (a ≤ i ≤ b)
그 다음에, 아래 쿼리를 Q번 수행한다.
x y k : Ai (x ≤ i ≤ y)의 모든 원소를 모아 오름차순으로 정렬했을 때, k번째 수를 구한다.
입력
첫째 줄에 터널의 수 N, M, Q가 주어진다. (1 ≤ N ≤ 1,000,000,000, 1 ≤ M ≤ 100,000, 1 ≤ Q ≤ 100,000)
둘째 줄부터 N개의 줄에는 쿼리 a, b, v가 주어진다. (1 ≤ a ≤ b ≤ N, 1 ≤ v ≤ 1,000,000,000)
다음 줄부터 M개의 줄에는 쿼리 x, y, k가 주어진다. (1 ≤ x ≤ y ≤ N, 1 ≤ k ≤ (모든 원소의 개수))
출력
Q개의 줄에 x y k 쿼리의 결과를 한 줄에 하나씩 출력한다.
예제 #1
5 4 1
1 5 1
1 1 3
4 5 1
3 4 2
1 3 4
2
예제 #2
10 4 4
1 4 11
2 3 22
6 9 33
8 9 44
1 1 1
4 5 1
4 6 2
1 10 12
11
11
33
44
힌트
로그인해야 코드를 작성할 수 있어요.