题目描述

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?

输入格式

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 $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.

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