시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 512 MB 126 8 4 44.444%

문제

You are given N empty arrays, t1,…,tn. At first, you execute M queries as follows.

  • add a value v to array ti (a ≤ i ≤ b)

Next, you process Q following output queries.

  • output the j-th number of the sequence sorted all values in ti (x ≤ i ≤ y)

입력

The dataset is formatted as follows.

N M Q
a1 b1 v1
...
aM bM vM
x1 y1 j1
...
xQ yQ jQ

The first line contains three integers N (1 ≤ N ≤ 109), M (1 ≤ M ≤ 105) and Q (1 ≤ Q ≤ 105). Each of the following M lines consists of three integers ai, bi and vi (1 ≤ ai ≤ bi ≤ N, 1 ≤ vi ≤ 109). Finally the following Q lines give the list of output queries, each of these lines consists of three integers xi, yi and ji (1 ≤ xi ≤ yi ≤ N,1≤ ji ≤ Σxi≤k≤yi|tk|).

출력

For each output query, print in a line the j-th number.

 

예제 입력

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

예제 출력 2

11
11
33
44

힌트

After the M-th query is executed, each ti is as follows:

[1,3], [1], [1,2], [1,1,2], [1,1]

The sequence sorted values in t1, t2 and t3 is [1,1,1,2,3]. In the sequence, the 4-th number is 2.