시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
10 초 | 512 MB | 914 | 189 | 96 | 13.483% |
You are given N empty arrays, t1,…,tn. At first, you execute M queries as follows.
Next, you process Q following output queries.
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
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
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.