10641번 - The J-th Number

You are given N empty arrays, t₁,…,t_n. At first, you execute M queries as follows.

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

Next, you process Q following output queries.

• output the j-th number of the sequence sorted all values in t_i (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 ≤ 10⁹), M (1 ≤ M ≤ 10⁵) and Q (1 ≤ Q ≤ 10⁵). Each of the following M lines consists of three integers a_i, b_i and v_i (1 ≤ a_i ≤ b_i ≤ N, 1 ≤ v_i ≤ 10⁹). Finally the following Q lines give the list of output queries, each of these lines consists of three integers x_i, y_i and j_i (1 ≤ x_i ≤ y_i ≤ N,1≤ j_i ≤ Σ_xi≤k≤yi|tk|).

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

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 t₁, t₂ and t₃ is [1,1,1,2,3]. In the sequence, the 4-th number is 2.