2D Range K-th Largest Query

Bob has placed several bottles of Laoshan Baihua Shecao Water on a spacious square. Each bottle is placed at a unique integer coordinate (x, y) and has a quality value v. When queried by Bob, you must answer instantly: Given a rectangular region defined by x₁ ≤ x ≤ x₂ and y₁ ≤ y ≤ y₂, find the quality of the bottle which is the k-th highest (largest quality value) within that region. If the region contains fewer than k bottles, output -1.

Note: No coordinate contains more than one bottle. The ordering is in descending order by quality value.

Input Format: The first line contains two integers N and Q, representing the number of bottles and the number of queries. Each of the following N lines contains three integers x, y, and v, indicating that a bottle with quality value v is placed at coordinate (x, y). Then Q lines follow, each containing five integers x₁, y₁, x₂, y₂, and k, representing a query.

Output Format: For each query, output a single line with one integer: the quality value of the k-th highest bottle in the specified rectangle, or -1 if there are less than k bottles in the region.

inputFormat

The first line of input contains two space-separated integers N and Q (1 ≤ N, Q ≤ 10⁵).
The next N lines each contain three integers x, y, and v (|x|, |y| ≤ 10⁹, 1 ≤ v ≤ 10⁹), describing the coordinate and quality value of a bottle. It is guaranteed that no two bottles share the same coordinate.
Then, Q lines follow. Each query is described by five integers x₁, y₁, x₂, y₂, and k (x₁ ≤ x₂, y₁ ≤ y₂, 1 ≤ k), representing the rectangular region and the rank to query.

outputFormat

For each of the Q queries, print one integer on a separate line: the quality value of the k-th highest bottle in the given rectangle, or -1 if there are fewer than k bottles in that region.

sample

5 3
1 2 10
2 2 20
3 3 15
0 0 5
2 3 25
1 2 3 3 1
1 2 3 3 3
0 0 1 2 2

25
15
5