Hide

Problem L
Triangular Logs

The local forest has a lot of trees! Each tree is located at integer coordinates and has an integer height. Cutting down any tree gives you a log with a length equal to its height. You want to obtain three triangular logs (that is, three logs that form a non-degenerate triangle) by cutting down three trees.

Given a list of queries which each specify an axis-aligned rectangular region, can you obtain three triangular logs by cutting down three trees in that region, possibly including those on the boundary of the rectangle?

Input

The first line of input contains two integers $n$ and $q$ ($1 \le n,q \le 10^5$), where $n$ is the number of trees and $q$ is the number of queries.

Each of the next $n$ lines contains three integers $x$, $y$ and $h$ ($1 \le x,y,h \le 10^9$), which describes a tree at location ($x,y$) with height $h$. All tree locations are distinct.

Each of the next $q$ lines contains four integers $x_{low}$, $y_{low}$, $x_{high}$ and $y_{high}$ ($1 \le x_{low} \le x_{high} \le 10^9$, $1 \le y_{low} \le y_{high} \le 10^9$), describing an axis-aligned rectangular region for a query.

Output

Output $q$ lines. Each line contains a single integer, which is the answer to the given query. Output 1 if there are three trees in the queried region that can form a non-degenerate triangle, and 0 otherwise. Output answers to the queries in the order of the input.

Sample Input 1 Sample Output 1
9 5
1 3 3
2 3 1
3 3 4
1 2 1
2 2 5
3 2 9
1 1 2
2 1 6
3 1 5
1 1 1 2
1 1 2 2
1 1 1 3
1 2 3 2
1 1 3 3
0
1
0
0
1
CPU Time limit 12 seconds
Memory limit 2048 MB
Author
Bowen Yu
Source 2022 ICPC North America Championship
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in