K-short Problem

In the view of a satellite, you can see lots of tall buildings in the city, and we assume that the city's border is flat. Now you have observed n tall buildings in the city and recorded their position and height. Due to some mysterious reasons, you need to answer a series of queries. Each query will give you a position(x, y) and k, then you have to find out the k-th shortest building in set{$(x, y) | x \leq X, y \leq Y$}.

Multiple test cases.For each test case, the first line will contain two integers n and m($0 < n \leq 30000, 0 \leq m \leq 30000$), which represents the amount of buildings and amount of queries. Then n lines follow, contains three integers $x, y, h (-1E9 \leq x, y \leq 1E9, 0 \leq h \leq 1E9)$ indicate the building's position and height in each line. Then there are m lines, each with three integers $x, y, k (-1E9 \leq x, y \leq 1E9, 1 \leq k \leq 10)$ used for query.

For each test case, if the k-th shortest building exists, output its height in 1 line, otherwise print "-1" (without quotes).

5 2
1 1 1
2 2 2
3 3 3
4 4 4
5 5 5
0 0 1
6 3 2

-1
2

BestCoder Round #18