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