Hide

# Problem LTriangular 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

Hide